本文主要是介绍uva10001，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//这个坑爹的题意，看了一次又一次，不懂，不懂！！！后来就在网上疯狂的搜索细胞自动机（中文百度），结果还是不是很懂，再后来就去找解题报告，发现了一个很好地网址，超赞！！！网址在下面
点击打开链接
看完之后一下子明朗了很多，主要是图起的作用，其实就是一个一维的细胞自动机！！！
一维的细胞自动有256种进化法则，分别对应八位二进制码，而题意给出的表是90 rule对应的进化法则！！！下面给出204对应的法则
十进制数 二进制 new state
left cell right 204(10),从下往上写
0 0 0 0 0
1 0 0 1 0
2 0 1 0 1
3 0 1 1 1
4 1 0 0 0
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1
//样例中第一个给出的数是进化法则，第二个给出的是要生成的串（进化为的串）的长度，第三个给出的要生成的串
//例如给出的第一个样例左右和中间的细胞都只能生成0，若存在要生成不全为0的串，那么一定是 garden of eden
//而第二样例是
10101（注意是一个环，他是给定串的前驱，可以生成给定串，即reachable）
10101
第二行的第一位的1是110进化来的
第二位的0是101进化来的
第三位的1是010进化来的
第四位的0是101进化来的
第五位的1是011进化来的
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
int k,n,ok;
int binary[8],a[35],aa[35],b[8][3]={{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}};
char c[35];
void dfs(int x)
{int i;if(ok) return ;if(x==n){/*for(i=0;i<n+2;i++)printf("%d ",a[i]);printf("\n");*/if(a[n]==a[0]&&a[n+1]==a[1])ok=1;return ;}for(i=0;i<8;i++)if(binary[i]==c[x]-'0'&&(x==0||a[x]==b[i][0]&&a[x+1]==b[i][1])){if(x==0){a[x]=b[i][0];a[x+1]=b[i][1];}a[x+2]=b[i][2];dfs(x+1);}
}
main()
{int i;//freopen("D:\\o.txt","r",stdin);while(scanf("%d%d%s",&k,&n,c)!=EOF){for(i=0;i<8;i++){binary[i]=k%2;k/=2;}ok=0;dfs(0);if(ok)printf("REACHABLE\n");else printf("GARDEN OF EDEN\n");}return 0;
}这篇关于uva10001的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
