LeetCode/cpp/out-of-boundary-paths.cpp

class Solution {
  private:
    const static unsigned CAP = 1000000007;

    class dp {
        const int rows;
        const int cols;
        const int maxMove;

        std::vector<std::vector<std::map<int, unsigned>>> paths;

        int dfs(int y, int x, int moves) {
            if (y < 0 || y >= rows || x < 0 || x >= cols) {
                // BASE: we got out of the bounds
                return 1;
            }

            if (moves <= 0) {
                // BASE: all moves were used or there are no moves left
                return 0;
            }

            if (paths[y][x].count(moves)) {
                // BASE(dynamic): already evaluated
                return paths[y][x][moves];
            }

            int options = 0;
            for (auto &[dx, dy] : std::vector<std::pair<int, int>>{
                     {0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {
                options = (options + dfs(y + dy, x + dx, moves - 1)) % CAP;
            }
            paths[y][x][moves] = options;

            return options;
        }

      public:
        dp(int rows, int cols, int maxMove)
            : rows(rows), cols(cols), maxMove(maxMove),
              paths(rows, std::vector<std::map<int, unsigned>>(cols)) {}

        int get(int row, int col) { return dfs(row, col, maxMove); }
    };

  public:
    int findPaths(int m, int n, int maxMove, int startRow,
                  int startColumn) const {
        return dp(m, n, maxMove).get(startRow, startColumn);
    }
};