题解 | 走迷宫

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;

int n,m,sx,sy,ex,ey,step;
int g[N][N],f[N][N];
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
queue<pair<int,int>> q;

void bfs(){
	
	q.push({sx,sy});
	
	g[sx][sy]=0;
	while(!q.empty()){
		pair<int,int> pr=q.front();
//		cout<<pr.first<<" "<<pr.second<<endl;
		q.pop();
		for(int i=0;i<4;i++){
			int tx=pr.first+dx[i];
			int ty=pr.second+dy[i];
			if(tx<1||tx>n||ty<1||ty>m) continue;
			if(g[tx][ty]==0) continue;
//			cout<<tx<<" "<<ty<<endl;
			g[tx][ty]=0;
			f[tx][ty]=f[pr.first][pr.second]+1;
			if(tx==ex&&ty==ey){
				cout<<f[ex][ey]<<endl;
				return;
			}
			q.push({tx,ty});
		}
	}
	
	if(f[ex][ey]==0) cout<<-1<<endl;
	else cout<<f[ex][ey]<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	cin>>sx>>sy>>ex>>ey;
	
	char x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>x;
			if(x=='.'){
				g[i][j]=1;
			}else{
				g[i][j]=0;
			}
		}
	}
	
	bfs();
	
    return 0;
}