algorithms

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

commit 96dad389705864255df9bb6cf63af5c3e9a32e0e
parent 31b1ae169558a33b41e5de9d8cc29e80303c27e1
Author: Andrew Laack <andrew@laack.co>
Date:   Thu,  5 Nov 2026 14:24:15 -0600

Track lc problem from last week

Diffstat:
Aleetcode/twisted-mirror-path-count/twisted-mirror-path-count.cpp | 45+++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 45 insertions(+), 0 deletions(-)

diff --git a/leetcode/twisted-mirror-path-count/twisted-mirror-path-count.cpp b/leetcode/twisted-mirror-path-count/twisted-mirror-path-count.cpp @@ -0,0 +1,45 @@ +class Solution { +public: + int dfs(vector<vector<int>>& grid, int x, int y, bool right, vector<int>& memo) { + // don't have to check left / top bc moving down / right only + if(!(x < grid[0].size() && y < grid.size())) { // check in bounds + return 0; + } + if(x == grid[0].size() - 1 && y == grid.size() - 1) { + return 1; // end state + } + + int current = (y * grid[0].size() + x) * 2 + (right && grid[y][x] == 1); + if(memo[current] != -1) { + return memo[current]; + } + + if(grid[y][x] == 1) { + if(right) { + int cr = dfs(grid, x,y+1,false, memo) % 1000000007; + memo[current] = cr; + return cr; + } else { + int cr = dfs(grid, x+1,y,true, memo) % 1000000007; + memo[current] = cr; + return cr; + } + } + + int res = 0; + + res += dfs(grid, x+1,y,true, memo); + res += ((long long) dfs(grid, x,y+1,false, memo)) % 1000000007; + res = res % 1000000007; + memo[current] = res; + return res; + } + int uniquePaths(vector<vector<int>>& grid) { + // simple dp problem with a routing twist + // if current == mirror -> direction matters + // this means in each state we care about direction iff current == mirror + // though that's just a constant so it isn't that necessary + vector<int> memo(grid.size() * grid[0].size() * 2, -1); + return dfs(grid, 0, 0, false, memo); + } +};