python - DFS检查二维网格中的对角线上是否存在字符

Question

我正在编写一种算法来检查二维数组是否具有字符序列。我的算法适用于水平和垂直搜索，但不适用于对角线搜索:

board = [
    ['Z', 'B', 'N', 'O', 'N', 'O'],
    ['Z', 'B', 'O', 'N', 'N', 'Z'],
    ['B', 'O', 'B', 'B', 'N', 'B'],
    ['O', 'N', 'O', 'N', 'N', 'N'],
    ['Z', 'Z', 'Z', 'Z', 'B', 'O'],
    ['B', 'Z', 'O', 'Z', 'B', 'N']
]

def dfs(board, word):
    if not board:
        return False
    N,M = len(board), len(board[0])
    stack = []
    for i in range(N):
        for j in range(M):
            if board[i][j] == word[0]:
                stack.append((i,j,0,{(i,j)}))
    while stack:
        i,j,step,visit=stack.pop()
        step+=1
        if step==len(word):
            return True        
        for (ni,nj) in [(i+x,j+y) for x,y in [(0,1), (0, -1), (1,0), (-1,0)]]:
            if (ni,nj) not in visit and 0<=ni<N and 0<=nj<M and board[ni][nj] == word[step]:
                stack.append((ni,nj,step,visit.union({(ni,nj)})))
    return False

我的函数 DFS 应该为输入 ZZZZ、NNNN 和 OOOO 返回 True，但是 OOOO 不工作 - 对角线步骤不工作。

我该如何解决？

Answer 1

线

for (ni,nj) in [(i+x,j+y) for x,y in [(0,1), (0, -1), (1,0), (-1,0)]]:

只把邻居当作四个方位。要包括对角线，我们应该有 8 个邻居:

directions = [
    (0, 1), (0, -1), (1, 0), (-1, 0), 
    (-1, -1), (1, 1), (-1, 1), (1, -1)
]

for ni, nj in [(i + x, j + y) for x, y in directions]:

修改后，算法探索对角线:

print(dfs(board, "OOOO")) # => True
print(dfs(board, "NBNZ")) # => True
print(dfs(board, "BNZO")) # => True

---

如果您打算将搜索限制在直线方向(从左上角删除诸如 "ZBOB" 之类的内容)，DFS 方法将不会有太大帮助。您可以简单地从每个方 block 开始在所有可能的方向上迭代而不进行任何转弯，在第一个不匹配的字母上尽早放弃。您当前的算法允许转弯，即使没有对角线修改，所以我假设您希望保留这种许可逻辑。