[关闭]
@zhutoulwz 2014-11-03T12:42:46.000000Z 字数 1318 阅读 1863

sicily 1171 The Game of Efil

sicily ACM


1. 题目大意

一块m * n的板上,格子上有一些细菌,一个细菌的八个方向上邻居细菌数如果是2或3个,那么下一代它能保留下来,否则会死掉(因为“孤独”或“拥挤”),如果一个空格的邻居细菌数是3个,那么下一代这个格子会产生一个新的细菌。给出一个板的当前的状态,求上一代有多少种不同的情况。注意:板的上下边是连通的,左右边也是连通的。

2. 题目数据范围

m * n <= 16

3. 解题思路

枚举所有状态,根据题目要求生成下一代的状态,并与输入的状态比较,如果相等,则是其中一种可能的情况,结果加1。因为最多有16个格子,每个格子有两种状态(有细菌或无细菌),因此总的状态数是2^16。枚举状态使用深度搜索

4. 代码

  1. // 1171.cpp
  2. #include <iostream>
  3. #include <cstdio>
  4. #include <memory.h>
  5. using namespace std;
  6. int m, n;
  7. int ans;
  8. int in[20][20];
  9. int d[20][20];
  10. int direction[8][2] = {{-1, -1}, {-1, 0}, {-1, 1},
  11. {0, -1}, {0, 1},
  12. {1, -1}, {1, 0}, {1, 1}};
  13. void cal()
  14. {
  15. int t;
  16. for (int i = 0; i < m; i ++)
  17. {
  18. for (int j = 0; j < n; j++)
  19. {
  20. int temp = 0;
  21. for (int k = 0; k < 8; k++)
  22. {
  23. //计算这个格子八个方向的格式有多少个邻居细菌,
  24. //因为上下是连通的,左右也是连通的,所以需要加上m(或n),然后再mod m(或n)
  25. if (d[(i + direction[k][0] + m) % m][(j + direction[k][1] + n) % n])
  26. temp ++;
  27. }
  28. if (temp == 3)
  29. t = 1;
  30. else if (d[i][j] == 1 && temp == 2)
  31. t = 1;
  32. else
  33. t = 0;
  34. if (in[i][j] != t)
  35. return;
  36. }
  37. }
  38. ans ++;
  39. return;
  40. }
  41. // 依次从上到下,从左到右递归
  42. void dfs(int x, int y)
  43. {
  44. if (x == m) // 全部格子已遍历完
  45. {
  46. cal();
  47. return;
  48. }
  49. d[x][y] = 0;
  50. if (y == n - 1) // 到了一行的最后格子,转为下一行第一个格子
  51. dfs(x + 1, 0);
  52. else
  53. dfs(x, y + 1);
  54. d[x][y] = 1;
  55. if (y == n - 1)
  56. dfs(x + 1, 0);
  57. else
  58. dfs(x, y + 1);
  59. }
  60. int main()
  61. {
  62. int cases = 1;
  63. while (scanf ("%d%d", &m, &n) && m != 0 && n != 0)
  64. {
  65. int k;
  66. ans = 0;
  67. scanf ("%d", &k);
  68. int x, y;
  69. memset(in, 0, sizeof(in));
  70. for (int i = 0; i < k; i++)
  71. {
  72. scanf ("%d%d", &x, &y);
  73. in[x][y] = 1;
  74. }
  75. dfs(0, 0);
  76. printf("Case %d: ", cases);
  77. if (ans)
  78. printf("%d possible ancestors.\n", ans);
  79. else
  80. printf("Garden of Eden.\n");
  81. cases ++; // 忘记加1,这里也WA了一次,如此低级的错误
  82. }
  83. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注