10分 除了#2都MLE 求助
查看原帖
10分 除了#2都MLE 求助
288506
OutsideR_楼主2021/5/5 16:23
#include <iostream>
#include <queue>
using namespace std;
short n,x1,x2,y1,y2;
char map[1001][1001];
short mx[4]={1,-1,0,0};
short my[4]={0,0,1,-1};
bool visit[1001][1001];
struct road{
	short x,y,step;
};
void bfs(int x1,int y1){
	queue <road> que;
	road first;
	first.x=x1;
	first.y=y1;
	first.step=0;
	visit[x1][y1]=1;
	que.push(first);
	while(!que.empty()){
		road f=que.front();
		que.pop();
		if(f.x==x2 && f.y==y2){
			cout<<f.step<<endl;
			exit(0);
		}
		for(int i = 0;i<4;i++){
			short tx=f.x+mx[i];
			short ty=f.y+my[i];
			if(!visit[tx][ty] && map[tx][ty]=='0' && tx<=n && tx>=1 && ty<=n && ty>=1){
				road n;
				n.x=tx;
				n.y=ty;
				n.step=f.step+1;
				visit[tx][ty];
				que.push(n);
			}
		}
	}
}
int main(){
	cin>>n;
	for(short i = 1;i<=n;i++)for(short j = 1;j<=n;j++)cin>>map[i][j];
	cin>>x1>>y1>>x2>>y2;
	bfs(x1,y1);
	return 0; 
} 

能省的都省了

2021/5/5 16:23
加载中...