40求助
查看原帖
40求助
941906
IO_Max楼主2024/10/7 11:27

Rt

#include<bits/stdc++.h>
using namespace std;
long long n,s1,s2,t1,t2,w,e,sx,sy;
char a[1145][1145];
long long dx[4]={1,0,0,-1};
long long dy[4]={0,1,-1,0};
bool vis[1145][1145];
int mp[1145][1145];
queue<int>x,y;
int bfs(int l,int r){
	x.push(l);
	y.push(r);
	vis[sx][sy]=true;
	while(!x.empty()){
		w=x.front();//取队首元素 
		e=y.front(); 
		x.pop();//弹出
		y.pop();
		if(w==s2&&e==t2)return mp[w][e];//最先达到的路径就是最短路径 
		for(int i=0;i<=3;i++){
			sx=e+dx[i];
			sy=w+dy[i];
			
			if(sx>=0&&sx<=n&&sy>=0&&sy<=n/*判断是否越界*/&&vis[sx][sy]==false/*判断是否走过*/&&a[sx][sy]=='0'/*判断是否可走*/){
				x.push(sx);
				y.push(sy);
				vis[sx][sy]=true;
				mp[sx][sy]=mp[w][e]+1;//计数器加1 
			}
		}
	
	}
	return -1;
}
int main(void){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	cin>>s1>>t1>>s2>>t2;
	cout<<bfs(s1,t1);
	return 0;
}
 
2024/10/7 11:27
加载中...