迷宫问题数据结构非递归c语言代码

迷宫问题通常可以使用深度优先搜索（Depth First Search, DFS）或广度优先搜索（Breadth First Search, BFS）来解决，这里提供一个基于邻接矩阵表示的简单C语言非递归版本的DFS解迷宫算法。假设迷宫矩阵`maze`中，0表示空格，1表示墙壁，2表示起点，3表示终点。

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

typedef struct {
    int row;
    int col;
} Cell;

// 检查当前位置是否有效
int is_valid(int maze[][N], Cell cell) {
    return cell.row >= 0 && cell.row < N && cell.col >= 0 && cell.col < N && maze[cell.row][cell.col] == 0;
}

// 检查当前位置是否为目标位置
int is_goal(Cell cell, int goal[2]) {
    return cell.row == goal[0] && cell.col == goal[1];
}

// 非递归的DFS寻找路径
void dfs(int maze[][N], Cell start, Cell end, int visited[][N], int path[]) {
    // 初始化路径数组
    path[0] = -1;
    int index = 1;

    Cell current = {start.row, start.col};
    while (!is_goal(current, end)) {
        visited[current.row][current.col] = 1; // 标记当前点已访问

        // 四方向移动
        if (is_valid(maze, current + {-1, 0}) && visited[current.row + (-1), current.col] != 1)
            path[index++] = -1; // 左
        if (is_valid(maze, current + {0, -1}) && visited[current.row, current.col + (-1)] != 1)
            path[index++] = 0; // 上
        if (is_valid(maze, current + {1, 0}) && visited[current.row + (1), current.col] != 1)
            path[index++] = 1; // 右
        if (is_valid(maze, current + {0, 1}) && visited[current.row, current.col + (1)] != 1)
            path[index++] = 2; // 下

        // 更新当前节点
        current.row += path[index - 1] / 3;
        current.col += path[index - 1] % 3;
    }
    printf("Path found: ");
    for (int i = index - 2; i >= 0; i--) {
        switch (path[i]) {
            case -1: printf("U"); break;
            case 0: printf("D"); break;
            case 1: printf("R"); break;
            case 2: printf("L"); break;
        }
    }
    printf("\n");
}

int main() {
    int maze[N][N]; // 假设N为迷宫大小
    // 填充迷宫...
    Cell start = {0, 0}; // 起点坐标
    Cell end = {N-1, N-1}; // 终点坐标

    int visited[N][N] = {0};
    int path[4*N]; // 用于存储路径

    dfs(maze, start, end, visited, path);
    return 0;
}