fork download
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. using namespace std;
  8. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  9. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  10. const int MAXN = 9;
  11.  
  12. int n, m;
  13. string t[MAXN];
  14.  
  15. void read()
  16. {
  17. cin >> n >> m;
  18. for(int i = 0; i < n; i++)
  19. cin >> t[i];
  20. }
  21.  
  22. int pop_cnt[1 << MAXN];
  23. vector<int> check_masks[MAXN];
  24. int broken_mask[MAXN];
  25. int TMP_MASK;
  26.  
  27. bool ok(int cl, int mask, int prv, int need)
  28. {
  29. if(prv & mask)
  30. return false;
  31.  
  32. if(mask & broken_mask[cl])
  33. return false;
  34.  
  35. if(need & broken_mask[cl])
  36. return false;
  37.  
  38. TMP_MASK = need;
  39. for(int i: check_masks[cl])
  40. if(pop_cnt[i & mask] >= 2)
  41. return false;
  42. else
  43. {
  44. if(pop_cnt[i & mask] == 0)
  45. TMP_MASK |= i;
  46. }
  47.  
  48. return true;
  49. }
  50.  
  51. int64_t dp[MAXN][1 << MAXN][1 << MAXN];
  52.  
  53. int64_t rec(int pos, int last, int need)
  54. {
  55. if(pos == m)
  56. return need == 0;
  57.  
  58. int64_t &memo = dp[pos][last][need];
  59. if(memo != -1) return memo;
  60.  
  61. memo = 0;
  62. for(int i = 0; i < (1 << n); i++)
  63. if(ok(pos, i, last, need))
  64. {
  65. int n_mask = i | (last & ((1 << n) - 1 - broken_mask[pos]));
  66. memo += rec(pos + 1, n_mask, TMP_MASK & ((1 << n) - 1 - n_mask));
  67. }
  68.  
  69. return memo;
  70. }
  71.  
  72. void solve()
  73. {
  74. for(int i = 1; i < (1 << MAXN); i++)
  75. pop_cnt[i] = pop_cnt[i >> 1] + (i & 1);
  76.  
  77. for(int j = 0; j < m; j++)
  78. {
  79. int curr = 0;
  80. for(int i = 0; i < n; i++)
  81. if(t[i][j] == 'X')
  82. {
  83. broken_mask[j] |= (1 << i);
  84. check_masks[j].push_back(curr);
  85. curr = 0;
  86. }
  87. else
  88. curr |= (1 << i);
  89.  
  90. check_masks[j].push_back(curr);
  91. }
  92.  
  93. memset(dp, -1, sizeof(dp));
  94. cout << rec(0, 0, 0) << endl;
  95. }
  96.  
  97. int main()
  98. {
  99. ios_base::sync_with_stdio(false);
  100. cin.tie(NULL);
  101.  
  102. read();
  103. solve();
  104. return 0;
  105. }
  106.  
  107.  
Success #stdin #stdout 0s 33672KB
stdin
Standard input is empty
stdout
1