配套思路视频:
数据结构 迷宫求解】 https://www.bilibili.com/video/BV1Zap9ecEbV/?share_source=copy_web&vd_source=3b7da5c734c920273f6d90574b6f2527
#include <stdio.h>
#include <malloc.h>/* -------------------------------- 地图的创建 -------------------------------- */
// 地图
#define N 10int map[N][N];// 初始化地图
void init()
{// 围墙生成for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {if(j == 9 || j == 0 || i == 0 || i == 9)map[i][j] = 1;}}// 障碍生成map[1][3] = map[2][3] = 1;map[1][7] = map[2][7] = 1;map[3][5] = map[3][6] = 1;map[4][2] = map[4][3] = map[4][4] = 1;map[7][3] = 1; map[7][4] = 1; map[5][4] = 1;map[6][2] = 1; map[7][2] = 1;map[6][6] = 1;map[7][6] = 1;map[7][7] = 1;map[8][1] = 1;// 起始位置设置map[1][1] = 5;// 出口位置设置map[8][8] = 2;
}/* -------------------------------- 栈操作的实现 -------------------------------- */
// 栈的操作
#define M 400typedef struct
{int x, y; // 坐标
} Coordinate;// 记录某个节点位置
Coordinate stk[M];
// hh 栈顶, tt 栈底
int hh = 0,tt = 0;// 入栈
void push(int x,int y)
{int idx = hh++;stk[idx].x = x;stk[idx].y = y;
}
// 出栈
Coordinate pop()
{if(hh > tt) return stk[--hh];else{perror("Stack has been NULL");exit(1);}
}
// 是否空栈
typedef int Bool;
Bool empty()
{return hh == tt;
}/* -------------------------------- 怎么走出迷宫的实现 -------------------------------- */
// 是否可以走
Bool canGo(int x,int y)
{int detail = map[x][y]; //当前位置信息if((detail == 2 || detail == 3 || detail == 5 || detail == 1 || detail == -1) ||(x < 0 || x >= N || y < 0 || y >= N) )return 0;return 1;
}// 遍历地图
void list()
{for (int i = 0; i < N; ++i) {for (int j = 0; j < N; ++j) {printf("%d\t",map[i][j]);}puts("");}
}// 判断是否可以找到地图出口
Bool MazePath()
{// 偏移量 用于迷宫上下左右的移动int dx[4] = {-1,0,1,0};int dy[4] = {0,1,0,-1};// 起始位置入栈push(1,1);do {// 取出位置Coordinate c = pop();int a = c.x, b = c.y;printf("蓝 [%d %d]\n",a,b);// 用于标记改路线是否完全走不通int flag = 0;// 四个方向寻找for (int i = 0; i < 4; ++i) {int x = a + dx[i];int y = b + dy[i];// 判断是否找到出口if(map[x][y] == 2){printf("找到出口~ 位置:[%d,%d]\n",x,y);return 1; // 找到}// 如果可以走, 且没走过else if(canGo(x,y)){push(x,y);// 入栈printf("黄 [%d %d]\n",x,y);map[x][y] = 3;// 标记走过flag = 1;// 找到可以走的路}}if(!flag)map[a][b] = -1;} while (!empty());return 0;
}int main()
{// 0 可以走, 1是墙壁 ,2是出口 ,3是标记, -1是不可走, 5是起始位置init(); // 初始化list();MazePath();list();return 0;
}
