广度优先搜索

#include<bits/stdc++.h>
using namespace std;
int bfs(int x1,int y1,int x2,int y2,
        vector<vector<char>>migong,vector<vector<bool>>&visit){
    int n=migong.size(),m=migong[0].size();
    queue<pair<int,int>> que;
    que.push(make_pair(x1-1,y1-1));
    visit[x1-1][y1-1] = true;
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    int ans = 0;
    while(!que.empty())
    {
        int size=que.size();
//         cout<<"size="<<size<<endl;
        for(int i=0;i<size;i++){
            int x = que.front().first;
            int y = que.front().second;
            if(x==(x2-1)&&y==(y2-1))
            {
                return ans;
            }
            que.pop();
            for(int j=0;j<4;j++){
                int _x=x+dx[j],_y=y+dy[j];
                if(_x>=0&&_x<n&&_y>=0&&_y<m&&
                   migong[_x][_y]=='.'&&!visit[_x][_y]){
                    visit[_x][_y]=true;
                    que.push(make_pair(_x, _y));
                }
            }
        }
        ans++;
    }
    return -1;
}
int main()
{
    int m,n;
    cin>>n>>m;
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    vector<vector<char>> migong(n,vector<char>(m));
    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;
        for(int j=0;j<m;j++)
        {
            migong[i][j] = str[j];
        }
    }
    if(migong[x2-1][y2-1]=='*'){
        cout<<-1<<endl;
        return 0;
    }
    vector<vector<bool>> visit(n,vector<bool>(m,false));
    cout<<bfs(x1,y1,x2,y2,migong,visit)<<endl;

    return 0;         
}