題目連結:http://exam.upc.edu.cn/problem.php?id=5206
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdio>
#include<stack>
#include<cmath>
#include<iostream>
#define ll long long
#define lowbit(x) x&(-x)
#define maxn 1050000
#define inf 0x3f3f3f3f
using namespace std;
int n,m,a[700][700],b[700][700];
int around(int a[][700],int x,int y)
{
int sum=-a[x][y];
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
sum+=a[x+i][y+j];
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int s=350,x=350+5,l=350,r=350+5;
int maxi=0,maxx=0,sum=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(a));
scanf("%d%d",&n,&m);
char str[10];
for(int i=0;i<n;i++)
{
scanf("%s",str);
for(int j=0;j<m;j++)
if(str[j]=='#')
{
a[350+i][350+j]=1;
sum++;
maxx++;
}
}
for(int i=1;i<=321;i++)
{
sum=0;
if(i%2==1)
{
for(int i=s-1;i<=x+1;i++)
for(int j=l-1;j<=r+1;j++)
{
int num=around(a,i,j);
b[i][j]=a[i][j];
if((num<2 || num>3)&&a[i][j]==1)
b[i][j]=0;
else if(num==3&&a[i][j]==0)
b[i][j]=1;
sum+=b[i][j];
if(b[i][j])
{
if(i==s-1)s--;
else if(i==x+1)x++;
if(j==l-1)l--;
else if(j==r+1)r++;
}
}
}
else
{
for(int i=s-1;i<=x+1;i++)
for(int j=l-1;j<=r+1;j++)
{
int num=around(b,i,j);
a[i][j]=b[i][j];
if((num<2 || num>3)&&b[i][j]==1)
a[i][j]=0;
else if(num==3&&b[i][j]==0)
a[i][j]=1;
sum+=a[i][j];
if(a[i][j])
{
if(i==s-1)
s--;
else if(i==x+1)
x++;
if(j==l-1)
l--;
else if(j==r+1)
r++;
}
}
}
if(sum>maxx)
{
maxi=i;
maxx=sum;
}
}
printf("%d %d %d\n",maxi,maxx,sum);
}
return 0;
}