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

106 阅读 0 评论 70 点赞

我是靠谱客的博主贤惠百褶裙，这篇文章主要介绍计蒜客 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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#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;
}