90分,TLE了一个点。没用联通块(一点小方法),但为什么TLE???想不通。
#include <bits/stdc++.h>
using namespace std;
int n,m,ax[4]={0,0,-1,1},ay[4]={1,-1,0,0},ans[1005][1005],x[100001],y[100001],sum;
char a[1001][1001];
bool vis[1001][1001],k[1001][1001];
struct Point
{
int x,y;
};
vector <Point> f;
void bfs(int x,int y,int k)
{
queue <Point> q;
q.push(Point{x,y});
vis[x][y]=1;
while(!q.empty())
{
Point now = q.front();
q.pop();
for(register int i = 0 ; i<4 ; i++){
int dx=now.x+ax[i],dy=now.y+ay[i];
if(!vis[dx][dy]&&dx>=1&&dy>=1&&dx<=n&&dy<=n&&a[dx][dy]!=a[now.x][now.y])
sum++,vis[dx][dy]=1,q.push(Point{dx,dy}),f.push_back(Point{dx,dy});
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(register int i = 1 ; i<=n ; i++)
for(register int j = 1 ; j<=n ; j++)
cin>>a[i][j];
for(register int i = 1 ; i<=m ; i++)
cin>>x[i]>>y[i];
for(register int i = 1 ; i<=m ; i++)
{
if(ans[x[i]][y[i]]&&k[x[i]][y[i]]){
cout<<ans[x[i]][y[i]]<<endl;
continue;
}
memset(vis,0,sizeof(vis));
sum=1;
f.clear();
bfs(x[i],y[i],i);
cout<<sum<<endl;
int len=f.size();
for(register int j = 0 ; j<len ; j++)
ans[f[j].x][f[j].y]=sum,k[f[j].x][f[j].y]=1;
}
return 0;
}