算法笔记|bfs之解救小哈算法|链表|宽度优先

问题
文章图片

【算法笔记|bfs之解救小哈】
文章图片

代码实现

#include struct node { int x; //横坐标 int y; //纵坐标 int s; //步数 }; int main() { struct node que[2501]; //方便求上一个坐标的值，地图规定最大为50*50，每一个点为一个队列 //所以node最大为2500 //也可以用二维数组表示 int i,j, startx, starty, q, p,head,tail,n,m,k,tx,ty,flog; int a[50][50] = { 0 }; //地图 int book[50][50] = { 0 }; //为每个走过的点做标记的备份地图 printf("请输入你要输入几行几列的迷宫："); scanf_s("%d %d", &n, &m); printf("请输入你要输入的迷宫（0表示路，1表示障碍）："); for(i=1; i<=n; i++) for (j = 1; j <= m; j++) { scanf_s("%d", &a[i][j]); } printf("请输入初始位置："); scanf_s("%d %d", &startx, &starty); printf("请输入小哈的位置："); scanf_s("%d %d", &p, &q); tail = 1; //队尾 head = 1; //队首 //为初始位置入队 que[tail].x = startx; que[tail].y = starty; que[tail].s = 0; //初始步数为0 tail++; //队尾指向队列的下一个 book[startx][starty] = 1; //为初始位置做标记 flog = 0; //用来标记是否到达目标点，0表示未到达，1表示到达 //用于表示走的方向的数组 int next[4][2] = { {1,0},//第一个数表示x，第二个表示y {0,1}, {-1,0}, {0,-1} }; //当队列不为空时循环 while (head < tail) { //枚举四个方向 for (k = 0; k <= 3; k++) {tx = que[head].x + next[k][0]; //下一个点的x坐标 ty = que[head].y + next[k][1]; //下一个点的y坐标 if (tx<1 || tx>n || ty<1 || ty>m) {//判断是否越界 continue; } if (book[tx][ty] == 0 && a[tx][ty] == 0) {//如果这个点没走过且不是障碍物则入队 book[tx][ty] = 1; //标记为走过 que[tail].x = tx; que[tail].y = ty; que[tail].s = que[head].s + 1; tail++; //队尾变化为队尾的下一个位置 } //判断是否到达小哈的位置 if (tx == p && ty == q) { flog = 1; //标记为到达了目标点 break; //结束for循环 }} if (flog == 1) {//如果到达了目标点结束while循环 break; } head++; //head表示上一个位置，由此位置开始扩展 } printf("最少要走%d步。", que[tail -1].s); //tail指向队尾的下一个位置，所以得-1 getchar(); getchar(); return 0; }

输入