测试点3超时
查看原帖
测试点3超时
981783
ABC2605731797楼主2024/5/4 20:34

,#3TLE,其余均通过,求助大佬

#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;

const int N=1005;
char map[N][N];
int ans[100005];
int isqe[N][N];
int flag[N][N];
int d1[] = {-1,0,1,0};
int d2[] = {0,-1,0,1};
int n,m,num;
struct node{
	int x,y;
};


void bfs(int x,int y)
{
	queue<node> qe;
	node front = {x,y};
	qe.push(front);
	flag[x][y] = num;
	ans[num] = 1;
	isqe[x][y] = 1;
	while(!qe.empty()){
		node top = qe.front();
		qe.pop();
		for(int k=0;k<=3;k++){
			int newx = top.x+d1[k];
			int newy = top.y+d2[k];
			if(newx>=0&&newx<n&&newy>=0&&newy<n&&map[newx][newy]!=map[top.x][top.y]&&!isqe[newx][newy]){
				ans[num]++;
				flag[newx][newy] = num;
				isqe[newx][newy] = 1;
				qe.push({newx,newy});
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++){
	    cin>>map[i];
	}
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if(!flag[x-1][y-1]){
			memset(isqe,0,sizeof isqe);
			bfs(x-1,y-1);
			num++;
		}
		cout<<ans[flag[x-1][y-1]]<<endl;
	}
	return 0;
}
2024/5/4 20:34
加载中...