576. 出界的路径数 2021-08-15

class Solution {
private:
    const int CEIL = 1000000007;
    int m, n;
    vector<vector<map<int, int> > > cache;
    int DFS(int x, int y, int step) {
        if (x < 0 || y < 0 || x >= m || y >= n)
            return 1;
        if (step == 0)
            return 0;
        if (cache[x][y].count(step))
            return cache[x][y][step];
        int count = 0;
        count = (count + DFS(x + 1, y, step - 1)) % CEIL;
        count = (count + DFS(x - 1, y, step - 1)) % CEIL;
        count = (count + DFS(x, y + 1, step - 1)) % CEIL;
        count = (count + DFS(x, y - 1, step - 1)) % CEIL;
        cache[x][y][step] = count;
        return count;
    }
public:
    int findPaths(int m_, int n_, int maxMove, int startRow, int startColumn) {
        m = m_;
        n = n_;
        cache.resize(m, vector<map<int, int> >(n));
        return DFS(startRow, startColumn, maxMove);
    }
};