联通块 多次访问 除了记忆化还有别的优化方法吗
  • 板块学术版
  • 楼主bloodstalk
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/4/17 16:31
  • 上次更新2023/10/28 03:27:42
查看原帖
联通块 多次访问 除了记忆化还有别的优化方法吗
231543
bloodstalk楼主2022/4/17 16:31

一道水广搜题 这个liantong数组就是用来记忆化的,但是即便这样还是TLE了两个点,这玩意还有啥剪枝的方法了吗

#include<bits/stdc++.h>

const int N=1005;
using namespace std;

int n,m;
bool mapp[N][N];
int vis[N][N];
int liantong[N][N];
int startx,starty;
int ans;

struct node
{
	int x;
	int y;
}now,endd;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

void bfs(int x,int y)
{
	queue <node> q;
	now.x=x;
	now.y=y;
	q.push(now);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			endd.x=now.x+dx[i];
			endd.y=now.y+dy[i];
			if(endd.x>=1 && endd.x<=n && endd.y>=1 && endd.y<=n && !vis[endd.x][endd.y] && mapp[endd.x][endd.y]==!mapp[now.x][now.y])
			{
				vis[endd.x][endd.y]=1;
				ans++;
				q.push(endd);
			}
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%1d",&mapp[i][j]); 
	memset(liantong,-1,sizeof liantong);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&startx,&starty);
		if(liantong[startx][starty]!=-1)
		{
			cout<<liantong[startx][starty]<<endl;
			continue;
		}
		memset(vis,0,sizeof vis);	
      vis[startx][starty]=1;
		ans=1;
		bfs(startx,starty);
		printf("%d\n",ans);		
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(vis[i][j]) liantong[i][j]=ans;	
	}
}
2022/4/17 16:31
加载中...