具有指定方向的二进制矩阵中存在路径

Question

我有一个用 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对角线步(➘)

但只能使用带有“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，但我不确定它们是否对我的问题最有效。

Answer 1

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))

具有指定方向的二进制矩阵中存在路径

Existence of path in binary matrix with specified directions

algorithm

path-finding

shortest-path

binary-matrix