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;
}
}