Codeforces Gym 100650C The Game of Efil DFS

题目链接:

http://codeforces.com/gym/100650/attachments

题意:

每个细胞如果四周细胞太少了，就会孤独而死，如果细胞周围细胞太多了，就会挤死。给你个布局，问你他的上一代布局会有几种。不过这道题的关键在于wrap around这个词，即边界是循环的。

题解:

数据范围很小,n*m<=16，所以直接dfs出所有的状态
然后再check

代码:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 #define MS(a) memset(a,0,sizeof(a))
  5 #define MP make_pair
  6 #define PB push_back
  7 const int INF = 0x3f3f3f3f;
  8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  9 inline ll read(){
 10     ll x=0,f=1;char ch=getchar();
 11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 13     return x*f;
 14 }
 15 //////////////////////////////////////////////////////////////////////////
 16 const int maxn = 1e5+10;
 17 
 18 int n,m,k,ans;
 19 int G[20][20],d[20][20],d2[20][20],cnt[20][20];
 20 int dx[8] = {0,0,1,-1,1,1,-1,-1};
 21 int dy[8] = {1,-1,0,0,1,-1,1,-1};
 22 
 23 int C(int x,int k){
 24     if(x == -1) return k-1;
 25     if(x == k) return 0;
 26     return x;
 27 }
 28 
 29 bool check(){
 30     MS(d2); MS(cnt);
 31     for(int i=0; i<n; i++)
 32         for(int j=0; j<m; j++){
 33             for(int k=0; k<8; k++){
 34                 int x = C(i+dx[k],n);
 35                 int y = C(j+dy[k],m);
 36                 if(d[x][y] == 1)
 37                     cnt[i][j]++;
 38             }
 39         }
 40 
 41     for(int i=0; i<n; i++)
 42         for(int j=0; j<m; j++){
 43             if(d[i][j] == 1){
 44                 if(cnt[i][j]==2 || cnt[i][j]==3)
 45                     d2[i][j] = 1;
 46                 else
 47                     d2[i][j] = 0;
 48             }else{
 49                 if(cnt[i][j] == 3)
 50                     d2[i][j] = 1;
 51                 else
 52                     d2[i][j] = 0;
 53             }
 54         }
 55 
 56     for(int i=0; i<n; i++)
 57         for(int j=0; j<m; j++)
 58             if(G[i][j] != d2[i][j])
 59                 return 0;
 60 
 61     return 1;
 62 }
 63 
 64 void dfs(int x,int y){
 65     if(x == n){
 66         if(check()) ans++;
 67         return ;
 68     }
 69 
 70     d[x][y] = 0;
 71     if(y == m-1)
 72         dfs(x+1,0);
 73     else
 74         dfs(x,y+1);
 75     d[x][y] = 1;
 76     if(y == m-1)
 77         dfs(x+1,0);
 78     else
 79         dfs(x,y+1);
 80     d[x][y] = 0;
 81 }
 82 
 83 int main(){
 84     int cas=1;
 85     while(cin>>n>>m,(n+m)){
 86         MS(d); MS(G); ans=0;
 87 
 88         cin >> k;
 89         for(int i=0; i<k; i++){
 90             int x,y; cin>>x>>y;
 91             G[x][y] = 1;
 92         }
 93         dfs(0,0);
 94         if(ans != 0)
 95             cout << "Case " << cas++ << ": " << ans << " possible ancestors.
";
 96         else
 97             cout << "Case " << cas++ << ": Garden of Eden.
";
 98     }
 99 
100     return 0;
101 }
102 
103 // http://codeforces.com/gym/100650/attachments