题解 | 走迷宫

#include <bits/stdc++.h>
using namespace std;
const int MAXN =1010;
char f[MAXN][MAXN];
int f2[MAXN][MAXN];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};//方位
int n,m;
int x,y;
int x2,y2;
void bfs()
{
    queue<pair<int,int>> q;//打队列
    q.push(make_pair(x,y));
    f2[x][y] = 0;
    while(!q.empty())//bfs模板
    {
        int ux = q.front().first;
        int uy = q.front().second;
        if(ux == x2 && uy == y2)return;//到目标点就退出，剩下的点没必要搜了
        q.pop();
        for(int i=0;i<4;i++)
        {
            int dx = ux + dir[i][0];
            int dy = uy + dir[i][1];
            if(dx<1 || dx>n || dy<1 || dy>m) continue;
            if(f2[dx][dy] != -1 || f[dx][dy] == '*' )continue; 
            f2[dx][dy] = f2[ux][uy] + 1;
            q.push(make_pair(dx,dy));
        }
    }
}

int main()
{
    memset(f2,-1,sizeof(f2));//初始化为-1，为何是-1？因为想少开个数组来判断是否已经访问过
    cin >> n >> m;//输入坐标
    cin >> x >> y;
    cin >> x2 >> y2;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> f[i][j];
        }
    }
    bfs();//bfs搜最短路径
    cout << f2[x2][y2] << endl;//输出目标路径
    return 0;
}