bfs都TLE……大佬请教教我优化优化吧!
查看原帖
bfs都TLE……大佬请教教我优化优化吧!
533436
最靓的哥楼主2022/4/23 09:18
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,cnt;
bool a[1005][1005],b[1005][1005];
queue<int> qx,qy;
char s[1005]; 
const int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void bfs(int x,int y){
	qx.push(x);
	qy.push(y);
	b[x][y]=1;
	while(!qx.empty()&&!qy.empty()){
		for(int i=0;i<4;i++){
			int nx=qx.front()+d[i][0];
			int ny=qy.front()+d[i][1];
			if(nx>0&&nx<=n&&ny>0&&ny<=n&&b[nx][ny]==0&&a[nx][ny]==!a[qx.front()][qy.front()]){
				cnt++;
				qx.push(nx);
				qy.push(ny);
				b[nx][ny]=1;
			}
		}
		qx.pop();
		qy.pop();
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>(s+1);
		for(int j=1;j<=n;j++){
			if(s[j]=='1')a[i][j]=1;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>sx>>sy;
		memset(b,0,sizeof(b));
		cnt=1;
		bfs(sx,sy);
		cout<<cnt<<"\n"; 
	}
	return 0;
} 

感激不尽!!!

2022/4/23 09:18
加载中...