MnZn求助,BFS正解,爆零
查看原帖
MnZn求助,BFS正解,爆零
399941
曾治茗楼主2022/10/15 23:19

rt

#include<iostream>
#include<queue>
#include<cstdio>
#include<string.h>

using namespace std;

char a[1010][1010];
int st[1010][1010];
int ans=0,x1,x2,y1,y2,n;

struct point{
	int xx,yy;
};
queue <point> q;

void BFS(){
	q.push((point){x1,y1}); 
	
	while(!q.empty() ){
		
//		for(int i=1;i<=n;i++)
//		{
//			for(int j=1;j<=n;j++)
//			{
//				cout<<st[i][j];
//			}
//			cout<<endl;
//		}
//		cout<<endl;
		int cx=q.front().xx;
		int cy=q.front().yy;
		q.pop() ;
		
		if(cx>n || cx<1) continue;
		if(cy>n || cy<1) continue;
		if(st[cx][cy]==1) continue;
		if(a[cx][cy]=='1') continue;
		
		st[cx][cy]=1;
		
		
		if(cx==x2 && cy==y2){
			cout << ans;
			return;
		}
		
		ans++;
		
		q.push((point){cx+1,cy}); 
		q.push((point){cx-1,cy}); 
		q.push((point){cx,cy+1}); 
		q.push((point){cx,cy-1}); 
	}
	
	
}

int main(){
	memset(st,0,sizeof(st));
	
	cin >>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin >> a[i][j];
		}
	}
	cin >> x1 >>y1 >> x2 >> y2;
//	st[x1][y1]=1;
	BFS();
	
	
	return 0;
}
/*
3
0 0 1
1 0 1
1 0 0
1 1 3 3
*/

qwq

2022/10/15 23:19
加载中...