Advertisement
goshansmails

Untitled

Jul 8th, 2019
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <string>
  5. using namespace std;
  6.  
  7. const int n = 7;
  8. const int len = n * n - 1;
  9.  
  10. struct Move
  11. {
  12. int dr;
  13. int dc;
  14. char letter;
  15. };
  16.  
  17. const vector<Move> moves = {
  18. {-1, 0, 'U'},
  19. {1, 0, 'D'},
  20. {0, -1, 'L'},
  21. {0, 1, 'R'}
  22. };
  23.  
  24. string form;
  25. string res;
  26.  
  27. int ans = 0;
  28. vector<vector<bool>> used(n + 2);
  29. vector<vector<int>> used_neighbours(n + 2);
  30.  
  31. bool check() {
  32. for (int i = 0; i < len; ++i) {
  33. if (form[i] != '?' && form[i] != res[i]) {
  34. return false;
  35. }
  36. }
  37. return true;
  38. }
  39.  
  40. void rec(int idx, int r, int c) {
  41.  
  42. if (used[r][c]) {
  43. return;
  44. }
  45.  
  46. if (idx < len && r == n && c == 1) {
  47. return;
  48. }
  49.  
  50. if (idx == len) {
  51. if (r == n && c == 1) {
  52. if (check()) {
  53. ++ans;
  54. }
  55. }
  56. return;
  57. }
  58.  
  59. int dr, dc;
  60. int bad_counter = 0;
  61. int i, j;
  62.  
  63. for (i = 0; i < 4; ++i) {
  64. int dr = moves[i].dr;
  65. int dc = moves[i].dc;
  66. if ((r+dr == 1 && c+dc == 1) || (r+dr == n && c+dc == 1)) {
  67. continue;
  68. }
  69. if (r+dr == 0 || r+dr == n + 1 || c+dc == 0 || c+dc == n + 1) {
  70. continue;
  71. }
  72. if (!used[r+dr][c+dc] && used_neighbours[r+dr][c+dc] >= 2) {
  73. if (bad_counter == 1) {
  74. return;
  75. } else {
  76. bad_counter++;
  77. j = i;
  78. }
  79. }
  80. }
  81.  
  82. for (const Move& it : moves) {
  83. dr = it.dr;
  84. dc = it.dc;
  85. used_neighbours[r+dr][c+dc]++;
  86. }
  87.  
  88. if (bad_counter == 1) {
  89. used[r][c] = true;
  90. dr = moves[j].dr;
  91. dc = moves[j].dc;
  92. res[idx] = moves[j].letter;
  93. rec(idx + 1, r+dr, c+dc);
  94. used[r][c] = false;
  95. for (const Move& it : moves) {
  96. dr = it.dr;
  97. dc = it.dc;
  98. used_neighbours[r+dr][c+dc]--;
  99. }
  100. return;
  101. }
  102.  
  103. used[r][c] = true;
  104. for (const Move& it : moves) {
  105. dr = it.dr;
  106. dc = it.dc;
  107. res[idx] = it.letter;
  108. rec(idx + 1, r+dr, c+dc);
  109. }
  110. used[r][c] = false;
  111. for (const Move& it : moves) {
  112. dr = it.dr;
  113. dc = it.dc;
  114. used_neighbours[r+dr][c+dc]--;
  115. }
  116. }
  117.  
  118. int main() {
  119. cin >> form;
  120. res.resize(len);
  121.  
  122. for (auto& x : used) {
  123. x.resize(n + 2, false);
  124. }
  125. for (auto& x : used_neighbours) {
  126. x.resize(n + 2, 0);
  127. }
  128.  
  129. for (int i = 0; i < n + 2; ++i) {
  130. used[i][0] = true;
  131. used[0][i] = true;
  132. used[i][n + 1] = true;
  133. used[n + 1][i] = true;
  134. }
  135. for (int i = 1; i <= n; ++i) {
  136. used_neighbours[i][1]++;
  137. used_neighbours[1][i]++;
  138. used_neighbours[i][n]++;
  139. used_neighbours[n][i]++;
  140. }
  141.  
  142. rec(0, 1, 1);
  143. cout << ans;
  144. return 0;
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement