0

我有一个用 0 和 1 填充的二进制矩阵 (N*M)。示例：

(S, 1, 1, 1, 0)
(1, 0, 0, 0, 1)
(1, 1, 0, 0, 1)
(1, 0, 1, 1, D)

起点 S 是左上角，目的地 D 是右下角。从 S 开始，允许执行以下步骤：

  1. 下降 1 级 (↓)
  2. 向右走 1 步 (→)
  3. 向右和向下对角线 1 步（➘）

但只能使用带有“1”的条目，因为“0”代表障碍。因此，例如在我的示例矩阵中，有三种可能的路径。

(S, 1, 1, 1,  )   (S,  ,  ,  ,  )   (S,  ,  ,  ,  )
( ,  ,  ,  , 1)   (1,  ,  ,  ,  )   (1,  ,  ,  ,  )
( ,  ,  ,  , 1)   ( , 1,  ,  ,  )   (1, 1,  ,  ,  )
( ,  ,  ,  , D)   ( ,  , 1, 1, D)   ( ,  , 1, 1, D)

目标：我正在寻找的是确定是否存在路径的最有效算法。该算法只需要在上述限制下输出 TRUE（如果至少存在一条从 S 到 D 的路径）和 FALSE（如果不存在从 S 到 D 的路径）。它不需要确定最短路径。仅是否存在满足条件的路径。

我研究过 DFS 和 BFS，但我不确定它们是否对我的问题最有效。

4

1 回答 1

2

DFS 和 BFS 适合这项任务。没有更有效的解决方案。如果您不查看整个矩阵，则无法回答该问题，因此最佳算法应该适用于 O(N*M)。DFS 和 BFS 适用于 O(N*M)。

矩阵是一个有 N*M 个顶点的图。每个顶点有三个或更少的邻居。
您需要有一个布尔数组 [N, M]。当你访问一个顶点 [n, m] 时，标记你访问过这个。并且不要访问已经访问过的顶点。

像这样的东西：

global int N, M
global int S = 2, D = 3 --assuming that start in matrix marked as 2 and destination as 3
global int matrix[N, M]
global bool visited[N, M] --initially filled with False

bool DFS(n, m)
    if n >= N || m >= M || visited[n, m] || matrix[n, m] == 0 then
        return False
    visited[n, m] = True
    return matrix[n, m] == D || DFS(n + 1, m) || DFS(n, m + 1) || DFS(n + 1, m + 1)

print(DFS(0, 0))
于 2021-02-02T16:32:04.233 回答