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 };