algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

twisted-mirror-path-count.cpp (1566B)


      1 class Solution {
      2 public:
      3     int dfs(vector<vector<int>>& grid, int x, int y, bool right, vector<int>& memo) {
      4         // don't have to check left / top bc moving down / right only
      5         if(!(x < grid[0].size() && y < grid.size())) { // check in bounds
      6             return 0;
      7         }
      8         if(x == grid[0].size() - 1 && y == grid.size() - 1) {
      9             return 1; // end state
     10         }
     11 
     12         int current = (y * grid[0].size() + x) * 2 + (right && grid[y][x] == 1);
     13         if(memo[current] != -1) {
     14             return memo[current];
     15         }
     16 
     17         if(grid[y][x] == 1) {
     18             if(right) {
     19                 int cr = dfs(grid, x,y+1,false, memo) % 1000000007;
     20                 memo[current] = cr;
     21                 return cr;
     22             } else {
     23                 int cr = dfs(grid, x+1,y,true, memo) % 1000000007;
     24                 memo[current] = cr;
     25                 return cr;
     26             }
     27         }
     28 
     29         int res = 0;
     30 
     31         res += dfs(grid, x+1,y,true, memo);
     32         res += ((long long) dfs(grid, x,y+1,false, memo)) % 1000000007;
     33         res = res %  1000000007;
     34         memo[current] = res;
     35         return res;
     36     }
     37     int uniquePaths(vector<vector<int>>& grid) {
     38         // simple dp problem with a routing twist
     39         // if current == mirror -> direction matters
     40         // this means in each state we care about direction iff current == mirror
     41             // though that's just a constant so it isn't that necessary
     42         vector<int> memo(grid.size() * grid[0].size() * 2, -1);
     43         return dfs(grid, 0, 0, false, memo);
     44     }
     45 };