【BFS】走迷宫求步数

怼烎@ 2023-02-14 01:30 31阅读 0赞

题目

给定一个m*n大小的迷宫，其中 * 代表不可通过的墙壁，“.”代表平地，S表示起点，T表示终点。
    移动过程中，只能前往上下左右四个位置的平地，求从起点S到终点T的最少步数。

输入

5 5
    .....
    .*.*.
    .*S*.
    .***.
    ...T*
    2 2 4 3

输出

#include <cstdio>
    #include <queue> 
    using namespace std;
    const int maxn = 100;
    
    char matrix[maxn][maxn]; //迷宫矩阵 
    bool inqueue[maxn][maxn]; //标记对应位置是否如果队列 
    int m,n; //m*n矩阵 
    int X[4] = {
        0,0,1,-1}, //分别表示上下左右四个方向的增量数组 
     Y[4] = {
        1,-1,0,0};
     
    struct Node{
        
     int x,y,step; //位置（x，y），起点至该结点的步数step 
    }S,N,T; //S起点，T终点，N临时结点 
    
    //判断该位置是否可以访问 
    bool isValid(int x,int y){
        
     if(x < 0 || x > m || y < 0 || y > n) //出界 
      return false;
     if(matrix[x][y] == '*') //该位置为墙 
      return false;
     if(inqueue[x][y] == true) //该位置已入过队列 
      return false;
     return true;
    }
    
    //BFS广度优先搜索，返回最终步数 
    int BFS(){
        
     int i;
     queue<Node> Q; //定义队列 
     Q.push(S); //将起点入队列 
     while(!Q.empty()){
         
      Node top = Q.front(); //队首元素赋给top 
      Q.pop();  //出队列 
      int newX,newY;
      if(top.x == T.x && top.y == T.y){
        
       return top.step;  //top位置等于终点位置，返回步数 
      }
      for(i = 0; i < 4; i++){
         //分别遍历上下左右四个方向 
       newX = top.x + X[i];
       newY = top.y + Y[i];
       if(isValid(newX,newY)){
         
       //新位置可访问 
        N.step = top.step + 1; //当前位置的步数为队首步数加一 
        N.x = newX;
        N.y = newY;
        Q.push(N); //新位置入队列 
        inqueue[newX][newY] = true; //新位置标记为已入队列 
       }
      }
     }
     return -1; //无法到达终点 
    }
    
    int main(int argc, char** argv) {
        
     int i,j;
     scanf("%d%d",&m,&n); 
     for(i = 0; i < m; i++){
        
      getchar(); //过滤每行后的换行符 
      for(j = 0; j < n; j++){
        
       matrix[i][j] = getchar(); //注意输入一行元素间不加空格 
      }
      matrix[i][n] = '\0'; 
     }
     scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y); //输入起点和终点 
     S.step = 0;
     printf("%d\n",BFS());
     return 0;
    }