【题解】P1536 【bfs】营救巨轮

//与走迷宫基本一致
#include<bits/stdc++.h>
#define N 1001
using namespace std;
struct node{
	int x,y,step;
}a,nf,nw;//a左上角 nf 队首，nw下一个入队的结点 
char maze[N][N];
int used[N][N];
int fx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,sx,sy,ex,ey;
queue<node>que;//队列
void bfs(){
	//先将a入队
	a.x=sx-1;
	a.y=sy-1;
	a.step=0; 
	used[a.x][a.y]=1;//能否删除 
	que.push(a);
	//只要队列不为空，遍历队列
	while(!que.empty()){
		//取出队首元素
		nf=que.front(); 
		if(nf.x==ex-1&&nf.y==ey-1) {
			cout<<nf.step<<endl;
			return ;
		}
		for(int i=0;i<4;i++){
			int nx=nf.x+fx[i][0];
			int ny=nf.y+fx[i][1];
			//长if 判断nx ny是否符合要求
			if(nx>=0&&nx<n&&ny>=0&&ny<n&&maze[nx][ny]=='0'&&!used[nx][ny]) {
				//符合要求的入队
				 nw.x=nx;
				 nw.y=ny;
				 nw.step=nf.step+1;
				 que.push(nw);
				 used[nx][ny]=1; 
			}	 
		}
		que.pop();//出队 
	} 
} 
int main(){
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>maze[i][j];
	cin>>sx>>sy>>ex>>ey;
	bfs();
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct point {
	int x;
	int y;
	int step;
}; 
int sx,sy,ex,ey,n;
char a[1001][1001];
//bool vis[1001][1001];
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};
queue<point>q;
int bfs(){
	point st;
	st.x=sx-1;
	st.y=sy-1;
	st.step=0;
	q.push(st);
	while(!q.empty()){
		point nw = q.front();
		if(nw.x==ex-1&&nw.y==ey-1){
			return nw.step;
		}
		for(int i=0;i<4;i++){
			point nxt;
			int nx = nw.x+dx[i];
			int ny = nw.y+dy[i];
			if(nx>=0 && nx<n &&ny>=0 &&ny<n&&a[nx][ny]=='0'){
				a[nx][ny]='1';
				nxt.x=nx;
				nxt.y=ny;
				nxt.step=nw.step+1;
				q.push(nxt);
			}
		}
		q.pop();
	}
	
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
			cin>>a[i];
	} 
	cin>>sx>>sy>>ex>>ey;
	cout<<bfs()<<endl;
	return 0;
}