Advertisement
goshansmails

Untitled

Apr 29th, 2020
365
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.70 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