本文主要是介绍uva10001 - Garden of Eden，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意不好理解，参考了人家的代码才看懂的题意，
就是用某种编译方式，检测所给字符串是否合理，即求它的原串。两者长度一样，只不过新得的串是根据所给编译方式和左邻右舍的值来求得的。
对于编译方式 rule：0
其意思为:
0 0 0 -->0
0 0 1 -->0
0 1 0 -->0
0 1 1 -->0
......
通俗来讲就是对于编译方式k，先把k转化为八位二进制串，8 -->0 0 0 0 1 0 0 0.。 用八位二进制串中的每个字符分别对应{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}
跟详细的解释请见于：http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
代码如下：
#include <cstdio>
int ok, nosolve[35], gain[35], state[8], array[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}};
void to_binary(int k)
{for(int i = 0; i < 8; i++) {state[i] = k%2; k/=2;}
}
void dfs(int n, int cur)
{if(ok) return;if(cur==n){if(gain[n]==gain[0]&&gain[n+1]==gain[1]) ok = 1;return;}for(int i = 0; i < 8; i++){if(nosolve[cur]==state[i]&&(!cur||(gain[cur]==array[i][0]&&gain[cur+1]==array[i][1]))){if(!cur) {gain[0] = array[i][0]; gain[1] = array[i][1];}gain[cur+2] = array[i][2];dfs(n, cur+1);}}
}
int main ()
{int k, n;char s[35];while(scanf("%d%d%s",&k,&n,s)==3){for(int i = 0; i < n; i++) nosolve[i] = s[i]-'0';to_binary(k);ok = 0;dfs(n, 0);if(ok)puts("REACHABLE");else puts("GARDEN OF EDEN");}return 0;
}
再贴一下，优化之后的代码。跑了132ms。
#include <cstdio>
int ok, nosolve[35], gain[35], state[8], array[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}};
void to_binary(int k)
{for(int i = 0; i < 8; i++) {state[i] = k%2; k/=2;}
}
void dfs(int n, int cur)
{if(ok) return;if(cur==n){if(gain[n]==gain[0]&&gain[n+1]==gain[1]) ok = 1;return;}if(!cur) {for(int i = 0; i < 8; i++) if(nosolve[0]==state[i]){ gain[0] = array[i][0]; gain[1] = array[i][1]; gain[2] = array[i][2]; dfs(n,cur+1); }}else{int t = gain[cur]*4+gain[cur+1]*2;if(state[t]==nosolve[cur]) {gain[cur+2] = 0; dfs(n, cur+1); }if(state[t+1]==nosolve[cur]) {gain[cur+2] = 1; dfs(n,cur+1); }}
}
int main ()
{int k, n;char s[35];while(scanf("%d%d%s",&k,&n,s)==3){for(int i = 0; i < n; i++) nosolve[i] = s[i]-'0';to_binary(k);ok = 0;dfs(n, 0);if(ok)puts("REACHABLE");else puts("GARDEN OF EDEN");}return 0;
}
这篇关于uva10001 - Garden of Eden的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
