如何在数组上使用 DFS

Question

我有一个一维值列表，它看起来像“int[] value”。我相信我已经将其转换为二维列表，如下所示：

for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
        board[i][j] = values[i * 4 + j];
    }
}

董事会是新的二维值列表。黑板上有数字。0 表示空白，1 表示绿色，2 表示蓝色，3 表示红色。如何使用深度优先搜索来查找某种颜色的完整路径？

Answer 1

• 创建一个二维数组boolean[][] visited来指定您访问过的点；将所有元素设置为false
• 遍历两个嵌套循环中的每个点
• visited[r][c]对于的每个点false，进入可以递归实现的 DFS
• 在递归 DFS 调用中检查该点是否是您的目的地；如果是，则返回true
• 如果该点具有正确的颜色，则在四个方向上探索其邻居（最多四个）
• 如果邻居有正确的颜色，则将其标记为已访问，然后进行递归调用
• 如果递归调用返回true，则返回 true
• 否则，继续探索其他邻居
• 探索完邻居后，返回false。