判断逃出范围的路径总数

[liuyingbin19222]

给出格子范围，判断逃出格子范围的路径数量，格子图片如下： img 自己是没有做出来这一道题，看了课后的解答，发现这是一道状态机的问题，列出来状态变化方程就可以得出答案。 代码如下:

class Solution {
    /*
        列出状态转移方程就可以实现得到结果;
    */
public:
    int findPaths(int m, int n, int N, int i, int j) {
        if(N == 0) return 0 ;
        const static int _N = 1000000007;
        vector<vector<vector<unsigned long long int>>> dp(m + 2, vector<vector<unsigned long long int>>(n + 2, vector<unsigned long long int>(N + 1, 0)));
        for(int i = 0;i <= m+1;++i){
            dp[i][0][0] = 1;
            dp[i][n+1][0] = 1;
        }
        for(int j = 0;j <= n+1;++j){
            dp[0][j][0] = 1;
            dp[m+1][j][0] = 1;
        }
        for(int k = 1;k <= N;++k){
            for(int i = 1;i <= m;++i){
                for(int j = 1;j <= n;++j){
                    dp[i][j][k] = ( dp[i-1][j][k-1] + dp[i+1][j][k-1] + dp[i][j-1][k-1] + dp[i][j+1][k-1] ) % _N;
                }   
            }
        }
        int sum = 0;
        for(int k = 1;k <= N; k++){
            sum = ( sum +  dp[i+1][j+1][k]) % _N;
        }
        return sum;
    }
};

[liuyingbin19222]

这里需要说明一下，状态方程的结构式dp[i][j][k] 中，dp[0][0][1] 表示达到坐标(0,0)需要走一步的距离，同理根据规则可以得出其他的数据表示。