走网格

[编程题]走网格

热度指数：345 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个nxm的网格中，起点在(1,1)，终点在(n,m)，网格中有一块不能走的矩形区域，左下坐标为(x0,y0)，右上坐标为(x1,y1)，求从起点到终点的路径条数。

示例1

输入

4,4,2,2,3,3

输出

说明

只有两条可达路径

备注:

，， , 答案可能很大请对1000000007取模

算法知识视频讲解

C++

不经历怎么能成长

class Solution {
public:
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        vector<vector<int> > dp(m+1, vector<int>(n+1,0));
        dp[m][n] = 1;  // (m,n)->(m,n) 为1
        for(int i=m; i>0; i--){
            for(int j=n; j>0; j--){
                if(x0 <= j && j <= x1 && y0 <= i && i <= y1){
                    continue;  // 默认为0 可以直接跳出循环
                } 
                if(i < m){
                    dp[i][j] += dp[i+1][j]; // dp[i+1][j] 可以取到
                }
                 if(j < n){
                    dp[i][j] += dp[i][j+1]; // dp[i][j+1] 可以取到
                }
                dp[i][j] %= 1000000007;
            }
        }
        return dp[1][1];
    }
   
};

发表于 2021-09-27 15:45:12 回复(0)

Python 3

ZhongHaoWang

#
# 
# @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
        mod = 10 ** 9 + 7
        dp = [[0 for i in range(m)] for i in range(n)]
        dir_ = {(0,-1),(-1,0)}
        dp[0][0] = 1
        for x in range(n):
            for y in range(m):
                if x0 - 1 <= x <= x1 - 1 and y0 - 1 <= y <= y1 - 1:
                    continue
                for dx,dy in dir_:
                    if x + dx < 0&nbs***bsp;x + dx >= n&nbs***bsp;y + dy < 0&nbs***bsp;y + dy >= m&nbs***bsp;(x0 - 1 <= x <= x1 - 1 and y0 - 1 <= y
<= y1 - 1):
                        continue
                    dp[x][y] += dp[x + dx][y + dy] % mod
        return dp[-1][-1] % mod

发表于 2021-09-03 18:50:26 回复(0)

Java

牛客196305255号

 public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        int[][] arr=new int[n][m];
        arr[0][0]=1;
        for(int i=0;i<n;i++) {
        	for(int j=0;j<m;j++) {
        		if(i>=x0-1&&i<=x1-1&&j>=y0-1&&j<=y1-1) {
        			continue;
        		}
        		if(i==0&&j==0) {
        			continue;
        		}
        		if(i==0) {
        			arr[0][j]=arr[0][j-1];
        		}
        		else if(j==0) {
        			arr[i][0]=arr[i-1][0];
        		}else {
        			arr[i][j]=(arr[i-1][j]+arr[i][j-1])%1000000007;
        		}
        	}
        }
        return arr[n-1][m-1];
    }

发表于 2021-03-11 13:20:27 回复(0)