题解 | #走迷宫#

#include<iostream>
#include<queue>
using namespace std;
char **grid;e
bool flag=false;
int e1,e2,n,m;
int **dis;
void check(int a,int b){
    if(a==e1-1&&b==e2-1)
        flag=true;
    else
        flag=false;
}
void bfs(int s1,int s2)
{
    int x=s1,y=s2;
    queue<pair<int,int>> que;
    grid[x][y]='*';
    dis[x][y]=0;
    que.push(make_pair(x,y));
    while(!que.empty()&&!flag){
        pair<int,int> temp=que.front();
        x=temp.first;
        y=temp.second;
        que.pop();
        if(x-1>=0&&grid[x-1][y]=='.'){
            que.push(make_pair(x-1,y));
            dis[x-1][y]=dis[x][y]+1;
            grid[x-1][y]='*';
            check(x-1,y);
        }
        if(x+1<n&&grid[x+1][y]=='.'){
            que.push(make_pair(x+1,y));
            dis[x+1][y]=dis[x][y]+1;
            grid[x+1][y]='*';
            check(x+1,y);
        }
        if(y-1>=0&&grid[x][y-1]=='.'){
            que.push(make_pair(x,y-1));
            dis[x][y-1]=dis[x][y]+1;
            grid[x][y-1]='*';
            check(x,y-1);
        }
        if(y+1<m&&grid[x][y+1]=='.'){
            que.push(make_pair(x,y+1));
            dis[x][y+1]=dis[x][y]+1;
            grid[x][y+1]='*';
            check(x,y+1);
        }
    }
}
int main()
{
    cin>>n>>m;
    grid=new char*[n];
    dis=new int*[n];
    for(int i=0;i<n;i++){
        grid[i]=new char[m];
        dis[i]=new int[m];
    }
    int s1,s2;
    cin>>s1>>s2>>e1>>e2;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>grid[i][j];
    if(grid[e1-1][e2-1]=='*')
        cout<<-1;
    else{
        bfs(s1-1,s2-1);
        if(flag)
            cout<<dis[e1-1][e2-1];
        else
            cout<<-1;
    }
    return 0;
}