矩阵右下角有任意大小障碍物的方法数向右或向下跳过

Question

问题- 您必须找到从初始位置(1,1)到最终位置(N,M) [其中N是行数，M是列数]可以达到的方法数，假设：

1. 您可以向下移动任意数量的步骤。
2. 您可以向右移动任意数量的步骤。

注意：这里的数组索引是 1-indexed

一些条件：

• 你永远不能离开网格。
• 您不能忽略这些条件。
• 第一个单元格 (1,1) 和最后一个单元格 (N,M) 不包含障碍物。
• 一个空闲单元用 表示。障碍物用*表示。

---

示例测试用例：

>>> 3 3
    . . .
    . * .
    . . .

>>> 8

会有8种方式：

• (1,1),(1,2),(1,3),(2,3),(3,3)
• (1,1),(1,2),(1,3),(3,3)
• (1,1),(1,3),(2,3),(3,3)
• (1,1),(1,3),(3,3)
• (1,1),(2,1),(3,1),(3,2),(3,3)
• (1,1),(3,1),(3,2),(3,3)
• (1,1),(2,1),(3,1),(3,3)
• (1,1),(3,1),(3,3)

---

我的代码：

def ways(l):
    
   # Don't know how to proceed



Testcases=int(input())
lst=[]
for i in range(Testcases):
    N,M=input().split()
    N,M=int(N),int(M)
    for j in range(N):
        s=input().split(" ",M)
        lst.append(s)
    
    ways(lst)

我不知道如何继续。

Answer 1

将路径编码为左（L=递增行）和右（R=递增列）步骤的字符串，您将获得数组中可能路径的一组排列。然后，您将检查每条路径是否遇到障碍物。这可能看起来像这样（没有错误处理，只执行了非常有限的测试，省略了游戏板条目，即您的.和现在*实现的，N = row-steps，M = col-steps，即带有节点的数组具有维度）：01(N+1, M+1)

import numpy as np
import itertools
import random

def chk_pth(path, gboard):
    row, col = 0, 0
    for sidx, stp in enumerate(path): # step through gameboard along path
        if stp == 'L':
            row += 1
        else:
            col += 1
        if gboard[row, col] == 1: # obstacle?
            return False
    return True
    
lst=[]
N, M = input().split()
N, M=int(N), int(M)
# gameboard input omitted
lst = np.zeros((N+1, M+1))
lst[random.randint(1, N), random.randint(1, M)] = 1 # hard-coded for now, todo: change to manual input
lst[N, M] = 0 # guaranteed unblocked exit
print(lst)

# N = rows, M = cols
pthstr = 'L' * N + 'R' * M # we encode the paths uniquely as lefts and right (left=row+1, right=col+1)
uq_paths = set(list(itertools.permutations(pthstr, N+M))) # only need unique paths, permutations gives multiple results
path_ok = []
for pidx, path in enumerate(uq_paths):
    path_ok.append(chk_pth(path, lst))

print([pth for pidx, pth in enumerate(uq_paths) if path_ok[pidx]]) # only show valid paths

结果是（注意随机游戏板，首先显示板，然后是有效路径）：

[[0. 0. 0. 0.]
 [0. 0. 1. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
[('L', 'R', 'L', 'R', 'L', 'R'), ('L', 'R', 'L', 'R', 'R', 'L'), ('L', 'R', 'L', 'L', 'R', 'R'), ('L', 'L', 'R', 'R', 'R', 'L'), ('L', 'L', 'R', 'R', 'L', 'R'), ('R', 'L', 'L', 'L', 'R', 'R'), ('L', 'L', 'R', 'L', 'R', 'R'), ('R', 'L', 'L', 'R', 'L', 'R'), ('L', 'L', 'L', 'R', 'R', 'R'), ('R', 'L', 'L', 'R', 'R', 'L'), ('R', 'R', 'R', 'L', 'L', 'L')]