手打 bfs,又带 TLE 又带 MLE,10pts,求调!
查看原帖
手打 bfs,又带 TLE 又带 MLE,10pts,求调!
510555
ImposterAnYu楼主2021/11/5 23:31
#include<bits/stdc++.h>
using namespace std;
const int dx[9] = {0,-1,1,0,0};
const int dy[9] = {0,0,0,-1,1};
int n,x,y,xx,yy,i,j,sx,sy,w[1005][1005];
char ch;
struct i_dont_like_bfs{
	int xxx,yyy,s;
} now,nex;
queue<i_dont_like_bfs> a;
int bfs(){
	now.xxx = x;
	now.yyy = y;
	w[x][y] = 114514,w[xx][yy] = 1919810;
	a.push(now);
	while(!a.empty()){
		now = a.front();
		a.pop();
		for(i = 1; i <= 4; i++){
			sx = now.xxx + dx[i];
			sy = now.yyy + dy[i];
			if(max(sx,sy) <= n && min(sx,sy) >= 1 && (!w[sx][sy] || w[sx][sy] == 1919810)){
				nex.xxx = sx;
				nex.yyy = sy;
				nex.s = now.s + 1;
				w[now.xxx][now.yyy] = 114514;
				if(w[sx][sy] == 1919810){
					return nex.s;
				}
				a.push(nex);
			}
		}
	}
}
int main(){
	cin >> n;
	for(i = 1; i <= n; i++){
		for(j = 1; j <= n; j++){
			ch = getchar();
			while(ch < '0' || ch > '1'){
				ch = getchar();
			}
			w[i][j] = (ch == '1');
		}
	}
	cin >> x >> y >> xx >> yy;
	cout<< bfs() << endl;
	return 0;
}
2021/11/5 23:31
加载中...