迷宫问题（BFS）

给定一个n* m大小的迷宫，其中* 代表不可通过的墙壁，而“.”代表平地，S表示起点，T代表终点。
移动过程中，如果当前位置是(x, y)(下标从0开始)，且每次只能前往上下左右、(x, y + 1)、(x, y - 1)、(x - 1, y)、(x + 1, y)四个位置的平地，求从起点S到达终点T的最少步数。
上面样例S为(2, 2)，T的坐标为(4, 3)。
在本题中，由于求的是最少步数，而BFS是通过层次的顺序来遍历的，因此可以从起点S开始计数遍历的层数，那么在到达终点T时的层数就是需要求解的起点S到达终点T的最少步数。

.....

.*.*.

.*S* .

.*** .

...T*

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int maxn = 100;

int n, m;

char maze[maxn][maxn];

bool inq[maxn][maxn] = { false };

struct node {

    int x;

    int y;

    int step;

}S,T,Node;

int X[4] = { 0,0,1,-1 };//建立增量数组方便遍历周边位置。

int Y[4] = { 1,-1,0,0 };

bool Isgo(int x, int y) {//判断位置是否有效

    if (maze[x][y] == '*') return false;

    else if (x >= n || x<0||y >= m||y<0||inq[x][y]==true) return false;//越界或者已经入过队。

    else 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++) {                                               //易错：

                                                                                    //Node.X= top.x+X[i];

            int newX = top.x + X[i];//这里应该建立两个整形变量用来判断新位置是否需要访问。   //Node.y=top.y+Y[i];

            int newY = top.y + Y[i];                                                //if(Isgo(Node.x,Node.y)){

       if (Isgo(newX, newY)) {                                                      //Node.step=top.step;

                Node.step = top.step + 1;                                           //q.push(NOde);

                Node.x = newX;                                                      //inq[Node.x][Node.y]=ture

                Node.y = newY;

                q.push(Node);

                inq[Node.x][Node.y] = true;

            }

        }

    }

    return -1;//没有找到返回一个-1；

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i++) {

        getchar();//过滤掉每一行后面的换行符

        for (int j = 0; j < m; j++) {

            maze[i][j]=getchar();

        }

        maze[i][m + 1] = '\0';//不是使用scanf函数或者是gets函数，一定要在每个字符串的结尾处加'\0'。

    }

    scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);

    S.step = 0;

    printf("%d\n", BFS());

    return 0;

}

巴特西

迷宫问题（BFS）

最新文章

热门文章