题解 | 走迷宫

#include<bits/stdc++.h>

using namespace std;

const int N = 1005;

int n,m;
int sx,sy,tx,ty;
char ch[N][N];
int dx[4] = {0,1,-1,0};
int dy[4] = {1,0,0,-1};
bool vis[N][N];

struct node{
    int x;
    int y;
    int now;
};

queue<node>q;

inline bool check(int x,int y){
    if(x<1 || x>n) return false;
    if(y<1 || y>m) return false;
    if(ch[x][y] == '*') return false;
    if(vis[x][y]) return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    cin>>sx>>sy>>tx>>ty;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ch[i][j];
    node st = {sx,sy,0};
    q.push(st);
    int ans = 0x3f3f3f3f;
    while(!q.empty()){
        node tmp = q.front();
        q.pop();
        int x = tmp.x, y = tmp.y, now = tmp.now;
        if(x == tx && y == ty){
            ans = min(ans, now);
            break;
        }
        if(now >= ans) continue;
        for(int i=0;i<4;i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(!check(nx,ny)) continue;
            node nxt = {nx,ny,now+1};
            q.push(nxt);
            vis[nx][ny] = true;
        }
    }
    cout<<(ans == 0x3f3f3f3f? -1: ans);
    return 0;
}