NC641 走网格(四种语言+视频讲解)

- 题目描述：

- 题目链接：
https://www.nowcoder.com/practice/aeb113f9081d4b97b78696f31b20dde7?tpId=196&&tqId=37628&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking

- 设计思想：

-视频讲解链接B站视频讲解
- 复杂度分析：

- 代码：
c++版本:

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x0 int整型 
     * @param y0 int整型 
     * @param x1 int整型 
     * @param y1 int整型 
     * @return int整型
     */
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        //dp[i][j]表示走到位置(i,j)时有多少种不同路径数目
        vector<vector<int>> dp(n+1, vector<int>(m+1,0));
        ///如果起点在不能走的矩形区域就retur 0 
        if(x0 <= 1 && x1 >= 1 && y0 <= 1 && y1 >= 1) return 0;
        dp[1][1] = 1;//起点
        //dp值更新
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                if (i == 1 && j == 1) continue;
                //如果下一步在不能走的矩阵区域就直接continue
                if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue;
                dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007;
            }
        }
        return dp[n][m];
    }
};

Java版本：

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x0 int整型 
     * @param y0 int整型 
     * @param x1 int整型 
     * @param y1 int整型 
     * @return int整型
     */
    public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        //dp[i][j]表示走到位置(i,j)时有多少种不同路径数目
        int [][]dp = new int[n + 1][m + 1];
        ///如果起点在不能走的矩形区域就retur 0 
        if(x0 <= 1 && x1 >= 1 && y0 <= 1 && y1 >= 1) return 0;
        dp[1][1] = 1;//起点
        //dp值更新
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                if (i == 1 && j == 1) continue;
                //如果下一步在不能走的矩阵区域就直接continue
                if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue;
                //dp值的更新
                dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007;
            }
        }
        return dp[n][m];
    }
}

Python版本:

#
# 
# @param n int整型 
# @param m int整型 
# @param x0 int整型 
# @param y0 int整型 
# @param x1 int整型 
# @param y1 int整型 
# @return int整型
#
class Solution:
    def GetNumberOfPath(self , n , m , x0 , y0 , x1 , y1 ):
        # write code here
        #dp[i][j]表示走到位置(i,j)时有多少种不同路径数目
        dp = [[0 for i in range(m+1)] for j in range(n+1)]
        # 如果起点在不能走的矩形区域就retur 0 
        if x0 <= 1 and x1 >= 1 and y0 <= 1 and y1 >= 1: return 0
        dp[1][1] = 1#起点
        #dp值更新
        for i in  range(1,n+1):
            for j in range(1,m+1):
                if i == 1 and j == 1: continue
                #如果下一步在不能走的矩阵区域就直接continue
                if i >= x0 and i <= x1 and j >= y0 and j <= y1: continue
                #dp值的更新
                dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007
        return dp[n][m]

JavaScript版本:

/**
 * 
 * @param n int整型 
 * @param m int整型 
 * @param x0 int整型 
 * @param y0 int整型 
 * @param x1 int整型 
 * @param y1 int整型 
 * @return int整型
 */
function GetNumberOfPath( n ,  m ,  x0 ,  y0 ,  x1 ,  y1 ) {
    // write code here
       //dp[i][j]表示走到位置(i,j)时有多少种不同路径数目
        let dp = Array.from(new Array(n+1),() => new Array(m+1).fill(0));
        ///如果起点在不能走的矩形区域就retur 0 
        if(x0 <= 1 && x1 >= 1 && y0 <= 1 && y1 >= 1) return 0;
        dp[1][1] = 1;//起点
        //dp值更新
        for(let i = 1;i <= n;i ++){
            for(let j = 1;j <= m;j ++){
                if (i == 1 && j == 1) continue;
                //如果下一步在不能走的矩阵区域就直接continue
                if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue;
                //dp值的更新
                dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007;
            }
        }
        return dp[n][m];
}
module.exports = {
    GetNumberOfPath : GetNumberOfPath
};