BFS解迷宫问题

注释很详细，直接上代码

//BFS求解迷宫问题
//BFS可用于求解最短路径的问题
#include <bits/stdc++.h>
using namespace std;
int dx[4]={0,1,0,-1};//右下左上
int dy[4]={1,0,-1,0};//右下左上
//BFS 传入迷宫（数组，不同的数值代表空地以及障碍物）传入map，用来标记当前位置的上一个位置在哪里，传入队列，用来放入当前位置的下一步，传入迷宫边界，防止越界
void BFS(vector<vector<int>> &arr,map<pair<int,int>,pair<int,int>> &mp,queue<pair<int, int>> &que,int endx,int endy)
{
    pair<int , int> star={0,0};//首先将起点入队
    que.push(star);
    arr[0][0]=1;//并将其设置为已经访问
    while(!que.empty())//起点不为空时
    {
        for(int i=0;i<4;i++)//判断上下左右的位置是否合法
        {
            int x=que.front().first+dx[i];
            int y=que.front().second+dy[i];
            if(x>=0 && x<endx && y>=0 && y<endy && arr[x][y]!=1)//当前位置如果合法
            {
                que.push({x,y});//将其入队
                arr[x][y]=1;//将其设置为已访问
                mp.insert(pair<pair<int,int>,pair<int,int>> ({x,y},{que.front().first,que.front().second}) );//将当前位置的上一个位置插入map中，便于后续查找
            }
        }
        que.pop();//队首的所有下一个位置都入队后，将队首出队
    }
    //当前循环结束后能够遍历迷宫中所有的位置
}

int main()
{
    int row,col;
    while(cin>>row>>col)
    {
        vector<vector<int>> arr(row,vector<int>(col,0));
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                cin>>arr[i][j];
            }
        }//迷宫已经有了

        map<pair<int,int>,pair<int,int>>mp;//用于存储上一个元素
        queue<pair<int, int>> que;//用来遍历所有位置

        BFS(arr,mp,que,row,col);

        vector<pair<int, int>> ret;//用来保存最终的路径
        pair<int , int> end={row-1,col-1};//设置终点
        ret.push_back(end);//将终点入队
        while(!(end.first==0 && end.second==0))
        {
            for(auto a:mp )//从map中查找终点的上一个位置
            {
                if(a.first==end)//找到后将终点的上一个位置插入路径中
                {
                    ret.push_back(a.second);
                    end=a.second;//更新当前的终点位置
                    break;
                }
            }
        }
        //当前while循环结束后，ret中保存了当前的最短路径，但是是倒序的
        reverse(ret.begin(), ret.end());//逆制ret得到最终结果
        for(auto a:ret)//按要求输出
        {
            cout<<"("<<a.first<<","<<a.second<<")"<<endl;
        }

   }
    return 0;
}