C语言非递归算法求解迷宫问题：使用栈寻找路径

迷宫问题是一个经典的计算机科学问题，目标是在给定的迷宫中找到一条从入口到出口的路径。这个问题可以用多种算法来解决，其中一种常用的方法是使用栈数据结构的非递归算法。

本文将介绍如何使用C语言实现这个算法，并提供一个完整的代码示例和详细的解释。

问题描述

迷宫可以用一个m x n的二维数组来表示，其中0代表通路，1代表障碍。迷宫的入口通常位于左上角(0, 0)，出口位于右下角(m-1, n-1)。

算法思路

创建一个栈来存储迷宫中的位置信息，包括行坐标、列坐标和方向。
将迷宫入口位置压入栈中。
重复以下步骤，直到栈为空：
- 弹出栈顶位置。
- 如果当前位置是出口，则找到了一条路径，结束循环。
- 否则，尝试从当前位置向四个方向（上、右、下、左）移动。
- 如果某个方向的相邻位置是通路且未被访问过，则将该位置压入栈中，并将该位置标记为已访问。
如果栈为空，则说明没有找到路径。

代码示例

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef struct {
    int i;
    int j;
    int direction;
} Position;

typedef struct {
    Position data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

void push(Stack *s, Position p) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->data[++s->top] = p;
}

Position pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        Position p = {-1, -1, -1};
        return p;
    }
    return s->data[s->top--];
}

void solveMaze(int maze[][MAX_SIZE], int m, int n) {
    Stack s;
    initStack(&s);

    Position entry = {0, 0, 0};
    push(&s, entry);

    while (!isEmpty(&s)) {
        Position current = pop(&s);
        int i = current.i;
        int j = current.j;
        int direction = current.direction;

        while (direction < 4) {
            int ni, nj;
            switch (direction) {
                case 0: // up
                    ni = i - 1;
                    nj = j;
                    break;
                case 1: // right
                    ni = i;
                    nj = j + 1;
                    break;
                case 2: // down
                    ni = i + 1;
                    nj = j;
                    break;
                case 3: // left
                    ni = i;
                    nj = j - 1;
                    break;
            }

            if (ni >= 0 && ni < m && nj >= 0 && nj < n && maze[ni][nj] == 0) {
                maze[ni][nj] = 2; // mark as visited
                Position next = {ni, nj, 0};
                push(&s, next);
                printf("(%d,%d,%d)\n", next.i + 1, next.j + 1, direction + 1);
                i = ni;
                j = nj;
                if (i == m - 1 && j == n - 1) {
                    return;
                }
                direction = 0;
            } else {
                direction++;
            }
        }
    }

    printf("No path found\n");
}

int main() {
    int m, n;
    printf("Enter the size of the maze (m n): ");
    scanf("%d %d", &m, &n);

    int maze[MAX_SIZE][MAX_SIZE];
    printf("Enter the maze (0 for path, 1 for obstacle):\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &maze[i][j]);
        }
    }

    solveMaze(maze, m, n);

    return 0;
}

代码解释

Position 结构体用来存储迷宫中一个位置的信息，包括行坐标 i，列坐标 j 和方向 direction。
Stack 结构体用来实现一个栈，使用数组 data 存储位置信息，top 指向栈顶元素。
initStack、isEmpty、isFull、push 和 pop 函数是栈的基本操作函数。
solveMaze 函数是解决迷宫问题的核心函数，它使用一个栈来存储访问过的位置，并通过循环遍历迷宫，直到找到出口或者栈为空。
main 函数是程序的入口函数，它负责读取迷宫的大小和内容，并调用 solveMaze 函数来解决迷宫问题。

总结

本文介绍了如何使用C语言实现一个非递归算法来解决迷宫问题。该算法使用栈数据结构来存储访问过的位置，并通过循环遍历迷宫，直到找到出口或者栈为空。这个算法简单易懂，并且可以有效地解决迷宫问题。