beephsupreme

grid paths

Aug 31st, 2022
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.20 KB | Source Code | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int DIR_LEN = 4;
  5. int dr[DIR_LEN] = {-1, 0, 1, 0};
  6. int dc[DIR_LEN] = {0, 1, 0, -1};
  7. const int PATH_LEN = 48;  // length of all possible paths
  8. int p[PATH_LEN];
  9. const int GRID_SIZE = 9;  
  10. // added border to all four sides so a 7x7 becomes a 9x9
  11. bool onPath[GRID_SIZE][GRID_SIZE];
  12.  
  13. int tryPath(int pathIdx, int curR, int curC) {
  14.     // Optimization 3
  15.     if ((onPath[curR][curC - 1] && onPath[curR][curC + 1])
  16.         && (!onPath[curR - 1][curC] && !onPath[curR + 1][curC])) return 0;
  17.     if ((onPath[curR - 1][curC] && onPath[curR + 1][curC])
  18.         && (!onPath[curR][curC - 1] && !onPath[curR][curC + 1])) return 0;
  19.  
  20.     if (curR == 7 && curC == 1) {  // reached endpoint before visiting all
  21.         if (pathIdx == PATH_LEN) return 1;
  22.         return 0;
  23.     }
  24.  
  25.     if (pathIdx == PATH_LEN) return 0;
  26.  
  27.     int ret = 0;
  28.     onPath[curR][curC] = true;
  29.  
  30.     // turn already determined:
  31.     if (p[pathIdx] < 4) {
  32.         int nxtR = curR + dr[p[pathIdx]];
  33.         int nxtC = curC + dc[p[pathIdx]];
  34.         if (!onPath[nxtR][nxtC]) ret += tryPath(pathIdx + 1, nxtR, nxtC);
  35.     }
  36.     // see Java solution for optimization 4 implementation
  37.     else {  // iterate through all four possible turns
  38.         for (int i = 0; i < DIR_LEN; i++) {
  39.             int nxtR = curR + dr[i];
  40.             int nxtC = curC + dc[i];
  41.             if (onPath[nxtR][nxtC]) continue;
  42.             ret += tryPath(pathIdx + 1, nxtR, nxtC);
  43.         }
  44.     }
  45.     // reset and return
  46.     onPath[curR][curC] = false;
  47.     return ret;
  48. }
  49.  
  50. int main() {
  51.     string line;
  52.     getline(cin, line);
  53.  
  54.     // convert path to ints
  55.     for (int i = 0; i < PATH_LEN; i++) {
  56.         char cur = line[i];
  57.  
  58.         if (cur == 'U') p[i] = 0;
  59.         else if (cur == 'R') p[i] = 1;
  60.         else if (cur == 'D') p[i] = 2;
  61.         else if (cur == 'L') p[i] = 3;
  62.         else p[i] = 4; //cur == '?'
  63.     }
  64.  
  65.     // set borders of grid
  66.     for (int i = 0; i < GRID_SIZE; i++) {
  67.         onPath[0][i] = true;
  68.         onPath[8][i] = true;
  69.         onPath[i][0] = true;
  70.         onPath[i][8] = true;
  71.     }
  72.     // initialize the inside of the grid to be completely empty
  73.     for (int i = 1; i <= 7; i++) {
  74.         for (int j = 1; j <= 7; j++) {
  75.             onPath[i][j] = false;
  76.         }
  77.     }
  78.  
  79.     int startIdx = 0;
  80.     int startR = 1;
  81.     int startC = 1;  // always start path at (1, 1)
  82.     int ans = tryPath(startIdx, startR, startC);
  83.     cout << ans << endl;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment