python - 计算从头到尾有障碍物的路径数

Question

我正在尝试实现一种算法，该算法应计算 NxM 矩阵从左下角到右上角的路径数。我在上传代码的某个网站上运行了它，它运行了一堆测试用例，我看不到它针对哪些测试用例运行，所以我所知道的是它在某些测试用例中失败了。

问题的完整描述:

You are given a grid of cells with size N rows by M columns. A robot is situated at the bottom-left cell (row N-1, column 0). It can move from cell to cell but only to the right and to the top. Some cells are empty and the robot can pass through them but others are not and the robot cannot enter such cells. The robot cannot go outside the grid boundaries.

The robot has a goal to reach top-right cell (row 0, column M-1). Both the start and end cells are always empty. You need to compute the number of different paths that the robot can take from start to end. Only count paths that visit empty cells and move only to the right and up.

为此，我正在做的是:

1. 创建一个空网格 NxM，用于存储数字对于每个 grid[i][j]，从起点 S 到 grid[i][j] 的路径数

2. F(S) = 1 #只有一种方法可以到达起点

3. 对于每个单元格 i,j，我检查它是否被阻塞，如果是 F(i,j) = 0

4. 对于剩余的单元格，我将 2 种可能的方式相加:F(i-1,j) + F(i, j+1)

Python 代码:

def count_the_paths(grid):
    N = len(grid)
    M = len(grid[0])

    ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways
    ways[N-1][0] = 1 # There's only 1 way to reach the starting point

    for row in range(N-1, -1, -1):
        for col in range(0, M):
            if grid[row][col] == 1: # Blocked cell
                ways[row][col] = 0
            elif row != N-1 or col != 0: # If it's not the starting point
                ways[row][col] = 0
                if row < N-1:
                    ways[row][col] += ways[row+1][col]
                if col > 0:
                    ways[row][col] += ways[row][col-1]

    return ways[0][M-1]

例如，如果网格是:

grid = [
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
]

ways 矩阵是:

ways = [
    [1, 0, 0, 1, 4], 
    [1, 1, 0, 1, 3], 
    [1, 0, 0, 1, 2], 
    [1, 0, 1, 1, 1], 
    [1, 1, 1, 0, 0]
]

所以路径的数量是 4，据我所知这是正确的。

有人知道我遗漏了什么或做错了什么吗？

更新:正如@Tempux 指出的那样，我必须存储路径数的 MODULO 1000003。

所以我改变了我的代码:

def count_the_paths(grid):
    N = len(grid)
    M = len(grid[0])

    ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways
    ways[N-1][0] = 1 # There's only 1 way to reach the starting point

    for row in range(N-1, -1, -1):
        for col in range(0, M):
            if grid[row][col] == 1: # Blocked cell
                ways[row][col] = 0
            elif row != N-1 or col != 0: # If it's not the starting point
                ways[row][col] = 0
                if row < N-1:
                    ways[row][col] += ways[row+1][col] % 1000003
                if col > 0:
                    ways[row][col] += ways[row][col-1] % 1000003

    return ways[0][M-1]

但是说我给出了错误答案的错误仍然存​​在。

更新 2:

根据 User_Targaryen 的建议，我更改了行

if grid[row][col] == 1: # Blocked cell

到:

if grid[row][col] == "1": # Blocked cell

还是不行

更新 3:

然后我最后一次尝试，(尝试使用 char 和 integer)按照 Tempux 的建议修正模加法:

def count_the_paths(grid):
    N = len(grid)
    M = len(grid[0])

    ways = [[None for _ in range(M)] for _ in range(N)] # Generate empty matrix to store the number of ways


    ways[N-1][0] = 1 # There's only 1 way to reach the starting point



    for row in range(N-1, -1, -1):
        for col in range(0, M):
            if grid[row][col] == 1: # Blocked cell - also tried with char instead


                ways[row][col] = 0
            elif row != N-1 or col != 0: # If it's not the starting point


                ways[row][col] = 0
                if row < N-1:
                    ways[row][col] += ways[row+1][col]
                    ways[row][col] %= 1000003                    
                if col > 0:
                    ways[row][col] += ways[row][col-1]
                    ways[row][col] %= 1000003                    

    return ways[0][M-1]

仍然失败

最终更新 [已解决]User_Targaryen 是对的，他们的测试用例存在问题(而且它们是字符，而不是整数)我收到了回复:

Hi Daniel,

Thanks a lot for writing to us about this. There was an issue with some of the test cases of the problem. It is now fixed. In addition to that, in your solution you should change the way you check if a cell is occupied or not. Note that the input grid consists of strings of 0 and 1. They are not numbers.

We've increased your allowed number of attempts, so that you can submit more.

Thanks again

感谢所有帮助过我的人。

Answer 1

查看问题陈述，由于缺少有关解决方案中错误的信息，我认为输入会有点像:

grid = ['01100','00010','01010','01000','00010']

因为它说:输入网格将包含 N 个字符串，每个字符串有 M 个字符 - 0 或 1

更改代码中的以下行可获得 10 个点:

if grid[row][col] == '1': # Blocked cell

编辑:您可以找到一个非常相似的问题here .提交您的解决方案以检查您的基本逻辑是否正确。

这是我接受的CodeChef 问题的解决方案:

def numWays(m,n,p):
  grid = [[0 for _ in range(n)] for _ in range(m)]
  ways = [[0 for _ in range(n)] for _ in range(m)]
  mod = 1000000007
  i = 0
  while i<p:
    i=i+1
    x,y = map(int, raw_input().split())
    grid[x-1][y-1]=1

  if grid[0][0]==1 or grid[m-1][n-1]==1:
    return 0

  ways[0][0]=1

  i=0
  ways[0][0] = 1
  while i<m:
    j = 0
    while j<n:
      if grid[i][j]==0:
        if i-1>=0 and j-1>=0:
          ways[i][j] = (ways[i][j-1] + ways[i-1][j]) % mod
        elif i-1>=0:
          ways[i][j] = ways[i-1][j]
        elif j-1>=0:
          ways[i][j] = ways[i][j-1]
      j=j+1
    i = i+1

  return ways[m-1][n-1]

def main():
  m,n,p = map(int, raw_input().split())
  print numWays(m,n,p)

main()