染色法,超时三个点有什么改进的方法吗,,,谢谢大家啦
查看原帖
染色法,超时三个点有什么改进的方法吗,,,谢谢大家啦
61426
夜雨声烦hst楼主2021/10/4 00:34

XDM我这个题用的染色法,但是说有三个点超时了,想了好久都不知道有啥改进的办法,这么写能有改进的方法吗,谢谢大家啦

#include<bits/stdc++.h>
//哈哈哈这道题妥妥的染色法,略略略 
using namespace std;
char t[10001][10001];
int a[10001][10001];
int b[10001][10001];
int kx[5]={0,1,-1,0,0};
int ky[5]={0,0,0,1,-1};
int n,m;
int d[10001][10001]={0};
void search(int x,int y)
{
	int l,r;
	for(int i=1;i<=4;++i)
	{
		l=x+kx[i];
		r=y+ky[i];
		if(l>=1&&l<=n&&r>=1&&r<=n&&a[l][r]!=a[x][y]&&d[l][r]==0)
		{
			b[l][r]=2;
			d[l][r]=1;
			search(l,r);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		scanf("%s",t[i]);
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			a[i][j]=t[i][j-1]-'0';
		}
	}
	for(int i=1;i<=m;++i)
	{
		int x,y;
		cin>>x>>y;
		int ji=0;
		b[x][y]=2;
		search(x,y);
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				if(b[i][j]==2)
				{
			    	ji++;	
				}
				b[i][j]=a[i][j];
				d[i][j]=0;
			}
		}
		cout<<ji<<endl;
	}
}
2021/10/4 00:34
加载中...