题解 | #迷宫问题#

#include <string>
#include <iostream>
#include <queue>
using namespace std;

struct ZB
{
    int x;
    int y;
};
queue<ZB> Q;   //储存当前已经访问过的坐标
int n,m;
int a[100][100];   //0可走，1障碍
string str[100][100];   //存储到每一步走过的坐标
int dx[4] = {0, 1, 0, -1},
    dy[4] = {1, 0, -1, 0};   //搜索方向矩阵

void bfs()
{
    ZB zb; 
    zb.x = 0; 
    zb.y = 0; 
    Q.push(zb);  //初始队头为起始点（0，0）
    
    str[0][0] = "(0,0)";    //初始点（0，0）走过的坐标只有它自身

    while(Q.empty() == 0)
    {
        if( Q.front().x == n-1  &&  Q.front().y == m-1 )     //注意开始坐标是（0，0），所以终点坐标为行列数-1
        {
             cout<<str[Q.front().x][Q.front().y];//打印；
             return;   
        }
        for(int i = 0; i < 4; i++)
        {
            int tx = Q.front().x + dx[i];
            int ty = Q.front().y + dy[i];
            if(tx>=0 && tx<n && ty>=0 && ty<m && a[tx][ty]==0)    //越界？是否访问过？
            {
                a[tx][ty] = 1;   //1代表已访问
                zb.x = tx; zb.y = ty; Q.push(zb);
                str[tx][ty] = str[Q.front().x][Q.front().y] + '\n' + '(' + to_string(tx) + ',' + to_string(ty) + ')';
            }
        }
        Q.pop();   //删掉当前队头
    }
}

int main()
{
    scanf("%d %d",&n,&m);  //n行m列的迷宫
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d",&a[i][j]);   //初始化迷宫 0可走，1障碍  
   
    bfs();
    return 0;
}