Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define sfi(arg) scanf("%d", &arg)
  5. #define sfl(arg) scanf("%lld", &arg)
  6. #define pf printf
  7.  
  8. using namespace std;
  9.  
  10. vector<vector<int>> field(9);
  11. map<pair<vector<vector<int>>, pair<int, int>>, int> mp;
  12. int best = 0;
  13. string abc;
  14.  
  15. int fu( int cur, int x, int y ) {
  16.     if( mp.count(make_pair(field, make_pair(x, y))) == 1 ) { // Если уже были в данной точке с аналогичным field
  17.         best += mp[make_pair(field, make_pair(x, y))];
  18.         return mp[make_pair(field, make_pair(x, y))];
  19.     }
  20.  
  21.     if( cur == 48 && x == 1 && y == 7 ) {
  22.         best++;
  23.         return 1;
  24.     }
  25.  
  26.     if( x == 1 && y == 7 )
  27.         return 0;
  28.  
  29.     int total = 0;
  30.     if( abc[cur] == '?') {
  31.         if( field[x + 1][y] == 0 ) {
  32.             field[x + 1][y] = 1;
  33.             total += fu( cur + 1, x + 1, y );
  34.             field[x + 1][y] = 0;
  35.         }
  36.  
  37.         if( field[x - 1][y] == 0 ) {
  38.             field[x - 1][y] = 1;
  39.             total += fu( cur + 1, x - 1, y );
  40.             field[x - 1][y] = 0;
  41.         }
  42.  
  43.         if( field[x][y + 1] == 0 ) {
  44.             field[x][y + 1] = 1;
  45.             total += fu( cur + 1, x, y + 1 );
  46.             field[x][y + 1] = 0;
  47.         }
  48.  
  49.         if( field[x][y - 1] == 0 ) {
  50.             field[x][y - 1] = 1;
  51.             total += fu( cur + 1, x, y - 1 );
  52.             field[x][y - 1] = 0;
  53.         }
  54.     } else if(abc[cur] == 'R') {
  55.         if( field[x + 1][y] == 0 ) {
  56.             field[x + 1][y] = 1;
  57.             total += fu( cur + 1, x + 1, y);
  58.             field[x + 1][y] = 0;
  59.         }
  60.     } else if(abc[cur] == 'L') {
  61.         if( field[x - 1][y] == 0 ) {
  62.             field[x - 1][y] = 1;
  63.             total += fu( cur + 1, x - 1, y);
  64.             field[x - 1][y] = 0;
  65.         }
  66.     } else if(abc[cur] == 'U') {
  67.         if( field[x][y - 1] == 0 ) {
  68.             field[x][y - 1] = 1;
  69.             total += fu( cur + 1, x, y - 1);
  70.             field[x][y - 1] = 0;
  71.         }
  72.     } else {
  73.         if( field[x][y + 1] == 0 ) {
  74.             field[x][y + 1] = 1;
  75.             total += fu( cur + 1, x, y + 1);
  76.             field[x][y + 1] = 0;
  77.         }
  78.     }
  79.  
  80.     mp[make_pair(field, make_pair(x, y))] = total; // Запоминаем ситуацию
  81. }
  82.  
  83. int main() {
  84.     for( int x = 0; x < 9; x++ ) {
  85.         for( int y = 0; y < 9; y++ ) {
  86.             field[x].push_back(0);
  87.         }
  88.     }
  89.  
  90.     for( int x = 0; x < 9; x++ ) { // Мнимые границы
  91.         field[0][x] = 1;
  92.         field[8][x] = 1;
  93.         field[x][0] = 1;
  94.         field[x][8] = 1;
  95.     }
  96.  
  97.     field[1][1] = 1;
  98.  
  99.     cin >> abc;
  100.  
  101.     fu( 0, 1, 1 );
  102.     pf("%d\n", best);
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement