BFS——走迷宫的最小步数

本文主要是介绍BFS——走迷宫的最小步数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 100;
struct node{int x, y;int step;
}S, T, Node;int n, m;              
char maze[maxn][maxn];   // 迷宫信息 
bool inq[maxn][maxn] = {false};
int X[4] = {0, 0, 1, -1};
int Y[4] = {1, -1, 0, 0}; // 增量数组bool test(int x, int y)
{if(x >= n || x < 0 || y >= m || y < 0) return false;if(maze[x][y] == '*') return false;if(inq[x][y] == true) return false;return true;
} int BFS()
{queue<node> Q;Q.push(S);while(!Q.empty()){node top = Q.front();Q.pop();if(top.x == T.x && top.y == T.y) return top.step;for(int i = 0; i < 4; i++){int newX = top.x + X[i];int newY = top.y + Y[i];if(test(newX, newY)){Node.x = newX;Node.y = newY;Node.step = top.step + 1;Q.push(Node);inq[newX][newY] = true;}}}return -1;
}int main()
{scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){scanf("%s", maze[i]);}scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);S.step = 0;printf("%d", BFS());return 0;
}

这篇关于BFS——走迷宫的最小步数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---