一个疑惑
  • 板块P1141 01迷宫
  • 楼主lrj3247
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/11/5 14:40
  • 上次更新2023/11/5 16:13:07
查看原帖
一个疑惑
983702
lrj3247楼主2023/11/5 14:40

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;
}
2023/11/5 14:40
加载中...