计蒜客 The Game of Life（南宁区域赛现场赛重现）瞎搞

74 阅读 0 评论 49 点赞

我是靠谱客的博主贤惠百褶裙，最近开发中收集的这篇文章主要介绍计蒜客 The Game of Life（南宁区域赛现场赛重现）瞎搞，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击打开链接

这是去年南宁区域赛的一道铜牌（银牌）题目，现场的时候两个队友做这个题目，没有做出来~~

最近在补题，于是找到了这道题目，做了好些日子，本来以为这道题目是要什么特殊的算法（矩阵快速幂保存状态之类的，OrzOrz太弱了难以启齿），然后突然发现这个题目就是一个瞎搞题目，只不过过程中要减枝（大佬们嘴中的送分题~~）

代码意思很简单~~我就不多解释了，溜了溜了（留下了没技术的眼泪，Orz~）

#include <bits/stdc++.h>
#define Bounds 500
using namespace std;
const int L[]={1,0,-1,0,1,1,-1,-1};
const int R[]={0,1,0,-1,1,-1,1,-1};
const int MAXN=1100;
struct Point
{
Point() {}
Point(int _x,int _y) {x=_x;y=_y;}
bool operator < (const Point& r)const
{
if(x!=r.x) return x<r.x;
return y<r.y;
}
bool operator == (const Point& r)const
{
return x==r.x&&y==r.y;
}
bool operator != (const Point& r)const
{
return !(x==r.x&&y==r.y);
}
int x,y;
}point[MAXN*MAXN],tmp[MAXN*MAXN*8];
bool live[MAXN][MAXN];
//少于两个邻居会死
//邻居恰好为两个或者三个则生存下来
//三个以上则邻居死亡
//原先死的，恰好有三个邻居则生存
int unique_point(int n)
{
int temp=0,ret=0;
while(temp<n)
{
int cnt=1;
while(temp+cnt<n&&tmp[temp]==tmp[temp+cnt]) cnt++;
if(cnt<2)
{
if(live[tmp[temp].x+Bounds][tmp[temp].y+Bounds])
live[tmp[temp].x+Bounds][tmp[temp].y+Bounds]=false;
}
else if(cnt==2)
{
if(live[tmp[temp].x+Bounds][tmp[temp].y+Bounds])
point[ret++]=Point(tmp[temp].x,tmp[temp].y);
}
else if(cnt==3)
{
live[tmp[temp].x+Bounds][tmp[temp].y+Bounds]=true;
point[ret++]=Point(tmp[temp].x,tmp[temp].y);
}
else
{
live[tmp[temp].x+Bounds][tmp[temp].y+Bounds]=false;
}
temp+=cnt;
}
return ret;
}
//void debug(int tot)
//{
//
printf("New City :%dn",tot);
//
for(int i=0;i<tot;i++)
//
{
//
printf("City :%d %dn",point[i].x,point[i].y);
//
}
//}
int main()
{
//
freopen("in.txt","r",stdin);
//
freopen("out.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
memset(live,false,sizeof(live));
int n,m;
scanf("%d%d",&n,&m);
int tot=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
char flag;
cin>>flag;
if(flag=='#')
{
point[tot++]=Point(i,j);
live[i+Bounds][j+Bounds]=true;
}
}
//
debug(tot);
int starttime=0,maxpeople=tot;
for(int i=1;i<=321;i++)
{
//
printf("Generation :%dn",i);
int sum=0;
for(int j=0;j<tot;j++)
for(int k=0;k<8;k++)
{
int x=point[j].x+L[k];
int y=point[j].y+R[k];
tmp[sum++]=Point(x,y);
}
sort(tmp,tmp+sum);
for(int j=0;j<tot;j++)
if(*lower_bound(tmp,tmp+sum,point[j])!=point[j])
{
//
printf("point[%d][%d]n",point[j].x,point[j].y);
live[point[j].x+Bounds][point[j].y+Bounds]=false;
}
tot=unique_point(sum);
if(tot>maxpeople)
{
maxpeople=tot;
starttime=i;
}
//
debug(tot);
if(tot==0) break;
}
printf("%d %d %dn",starttime,maxpeople,tot);
}
return 0;
}