走网格

[编程题]走网格

热度指数：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取模

算法知识视频讲解

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)