///////////////////////////////////////////////////////////////
// 生命游戏C++版 //
// //
// //
///////////////////////////////////////////////////////////////
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
enum condition{dead,alive};
//个体的定义,包括生死情况和周围的生存人数
struct individual
{
condition con;
int SurvivorsAround;
};
//环境的定义,包含无参,单参和双参的重载构造函数(参数表示长宽),复制构造函数,析构函数,
//修改函数Modify(),后处理函数postprocessor(),主要用来计算下一代的SurvivorsAround.
struct environment
{
individual** p;int m,n,pred;//pred为已经处理了的round数,在后面search()有用
void Modify(int r,int s,condition t)
{
p[r][s].con=t;
}
void postprocessor()
{
for(int i=1;i<m+1;i++)
for(int j=1;j<n+1;j++)
p[i][j].SurvivorsAround=p[i-1][j-1].con+p[i-1][j].con+p[i-1][j+1].con
+p[i][j-1].con +p[i][j+1].con
+p[i+1][j-1].con+p[i+1][j].con+p[i+1][j+1].con;
}
environment(int r)
{
m=r;
n=r;
p=new (individual*[m+2]);
for(int i=0;i<m+2;i++)
p[i]=new individual[n+2];
for(i=0;i<m+2;i++)//初始化,全部为死
for(int j=0;j<n+2;j++)
{
p[i][j].con=dead;
}
postprocessor();
pred=1;
}
environment(int r,int s)
{
m=r;
n=s;
p=new (individual*[m+2]);
for(int i=0;i<m+2;i++)
p[i]=new individual[n+2];
for(i=0;i<m+2;i++)
for(int j=0;j<n+2;j++)
{
p[i][j].con=dead;
}
postprocessor();
pred=1;
}
environment(environment& a)
{
m=a.m;
n=a.n;
p=new (individual*[m+2]);
for(int i=0;i<m+2;i++)
p[i]=new individual[n+2];
for(i=0;i<m+2;i++)
for(int j=0;j<n+2;j++)
{
p[i][j].con=a.p[i][j].con;
}
postprocessor();
pred=a.pred;
}
environment()
{}
};
///////////////////////////////////////////////////////
// 生命衍化过程的演示程序部分 //
// 第98行到第213行
///////////////////////////////////////////////////////
//构造人工环境,人工输入环境中每个个体的情况。
environment CreateArtificialEnvironment(int m,int n)
{
environment a;
int k=0;
a.m=m;
a.n=n;
a.p=new (individual*[m+2]);
for(int i=0;i<m+2;i++)
a.p[i]=new individual[n+2];
cout<<"请以矩阵形式输入"<<m*n<<"个个体的初始情况,1代表生存,0代表死亡";
for(i=1;i<m+1;i++)
for(int j=1;j<n+1;j++)
{
cin>>k;
a.p[i][j].con=(enum condition)k;
}
for(i=0;i<m+2;i++)
{
a.p[i][0].con=dead;
a.p[i][n+1].con=dead;
}
for(int j=0;j<m+2;j++)
{
a.p[0][j].con=dead;
a.p[m+1][j].con=dead;
}
a.postprocessor();
return a;
}
//计算环境中的某一个体下一代的生存情况
condition surviveordie(const environment&a,int i,int j)
{
int q=a.p[i][j].SurvivorsAround;
if(a.p[i][j].con==alive)
{
if(q>=4||q<=1)
return dead;
else
return alive;
}
else if(q==3)
return alive;
else
return dead;
}
//计算出下一代的情况,并把原环境改变
void next(environment&a)//注意,这用的是引用
{
condition**s;
s=new condition*[a.m];
for(int i=0;i<a.m;i++)
s[i]=new condition[a.n];
for(i=0;i<a.m;i++)
for(int j=0;j<a.n;j++)
s[i][j]=surviveordie(a,i+1,j+1);
for(i=0;i<a.m;i++)
for(int j=0;j<a.n;j++)
a.p[i+1][j+1].con=s[i][j];
a.postprocessor();
}
//环境的打印函数
void print(environment&a)
{
for(int i=0;i<a.m;i++)//?
{
for(int j=0;j<a.n;j++)
{
if(a.p[i+1][j+1].con==alive)
cout<<"* ";
else
cout<<" ";
}
cout<<endl;
}
}
//生成随机环境
environment CreateRandomEnvironment(int m,int n)
{
environment a;
int k=0;
a.m=m;
a.n=n;
a.p=new (individual*[m+2]);
for(int i=0;i<m+2;i++)
a.p[i]=new individual[n+2];
for(i=1;i<m+1;i++)
for(int j=1;j<n+1;j++)
{
a.p[i][j].con=(enum condition)(rand()%2);
}
for(i=0;i<m+2;i++)
{
a.p[i][0].con=dead;
a.p[i][n+1].con=dead;
}
for(int j=0;j<m+2;j++)
{
a.p[0][j].con=dead;
a.p[m+1][j].con=dead;
}
a.postprocessor();
return a;
}
//////////////////////////////////////////////////////////////////////
// 导读 //
// 下面属于计算给定地图的最大稳定容纳量部分。 //
// 分为广度优先和深度优先两种方法。 //
// 广度优先从第225行到第333行 //
// 深度优先从第336行到第460行 //
//////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
// 这里开始为广度优先搜索 //
////////////////////////////////////////////////////////////
typedef environment DataType;
#include"queue.h"
//由于用到广度搜索,需要一个队列,队列的元素为环境类型
PLinkQueue Map=createEmptyQueue_link();
//判断某节点的状态在进程中是否稳定
int IsSafe(const environment&a ,int m,int n)
{
return(surviveordie(a,m,n)==a.p[m][n].con);//下一代的情况是否跟原来一样
}
//round是指从左上角开始数到round的一个 “_|”形的区域。
//这个函数的作用在于按照num的二进制码来设置这一区域的状况
//也就是num的二进制码的每一位'0''1'对应每一点的死与生
environment set(environment a,int round,int num)
{
int x=1;int i=1;
for(i=1;i<=round;i++)
{
a.p[round][i].con=condition((x&num)!=0);
x*=2;
}
for(i=round-1;i>=1;i--)
{
a.p[i][round].con=condition((x&num)!=0);
x*=2;
}
a.postprocessor();
return a;
}
//计算整个环境最后总存活个数
int countsurvivals(const environment&a)
{
int i,j,c=0;
for(i=1;i<=a.m;i++)
for(j=1;j<=a.n;j++)
if(a.p[i][j].con==alive)
c++;
return c;
}
//小小指数函数,求m的n次方
int exp(int m,int n)
{
if(n==0)
return 1;
return m*exp(m,n-1);
}
//判断环境中round对应的'_|'形区域是否稳定
int CircleSafe(const environment &a,int round)
{
int i=1;
for(i=1;i<=round;i++)
{
if(!IsSafe(a,round,i))
return 0;
}
for(i=round-1;i>=1;i--)
{
if(!IsSafe(a,i,round))
return 0;
}
return 1;
}
//总的BSearch(),计算n*n的环境的最大稳定存活量,从左上角向右下角蔓延
int BSearch(int n)
{
if(n==1) return 0;
environment a(n),b(n);
int count;
enQueue_link(Map,set(a,1,0));
enQueue_link(Map,set(a,1,1));//把最左上角的点的两种情况入队
while(!isEmptyQueue_link(Map))
{
a=frontQueue_link(Map);//不断处理队首元素
deQueue_link(Map);
for(int i=0;i<exp(2,2*a.pred+1);i++) //2*a.pred+1为第pred圈的节点个数
{
b=set(a,a.pred+1,i);//把a.pred对应的那个'_|'区域的各种情况检查,行得通的入队
if(CircleSafe(b,a.pred))
{
b.pred=a.pred+1;
if(b.pred==n)//这条路已经走到尽头,把这种方法能存活的最大人数计入count
{
if(CircleSafe(b,b.pred)&&count<countsurvivals(b))
count=countsurvivals(b);
continue;
}
enQueue_link(Map,b);
}
}
}
return count;
}
////////////////////////////////////////////////////
// 这里开始为深度优先搜索 //
////////////////////////////////////////////////////
struct Mark//环境状况的标志字。注意,为了不引起混淆和以后使用方便,这里弃用数组第0号元素与最后一号元素。
{
Mark(int i)
{
mark=new int[i+2];
for(int j=0;j<=i+1;j++)//注意这里mark[0]与mark[i+1]是不使用的,他们为CircleSafe()凑形式而已
mark[j]=0;//初始化时全为0
n=i;//方阵边长的大小
}
void SetMark(int i,int m)//将标志字的第i位设成m。
{
mark[i]=m;
}
void ClearMark(int i)//将第i位之后的各位清零,不包括i
{
for(int j=i+1;j<=n;j++)
mark[j]=0;
}
void PrintMark()
{
for(int i=1;i<=n;i++)
cout<<mark[i]<<'\t';
cout<<endl;
}
int* mark;//标志字数组
int n;
};
int IsSafe(const Mark&a,int i,int j)//(1<=i<=n;1<=j<=n)重载IsSafe()函数,用标志字判断第i列第j位是否稳定
{
int k,l;//i=1的情况在Mark(int)里清零时保证满足,j=n的情况以二进制的取与方式保证满足。
//k为周围人的生存个数,l为自身生存情况
if(j==1)//只有j=1须特殊讨论,这时它周围u只有五个单位
k=(a.mark[i-1]&1)+((a.mark[i-1]&2)/2)+((a.mark[i]&2)/2)+(a.mark[i+1]&1)+((a.mark[i+1]&2)/2);
else//一般情况下周围有8个单位
k=((a.mark[i-1]&exp(2,j-2))/exp(2,j-2))+((a.mark[i-1]&exp(2,j-1))/exp(2,j-1))+((a