fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Ocya8y
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!