如何在隐式图中找到多个连通分量？

Question

我有一个 CS 问题，是这样描述的：

给定一张 sheet 的纸，其中一些单元格被切掉，用字符表示（“.”（切）或“#”（不切）），我需要找到会形成多少块。

示例：

##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####

上面例子的答案是5.

一块会形成：

....
.##.
....

两块将形成：

....
.#..
..#.

常识建议我想办法用图表示sheet（每个数字符号都是一个顶点，如果两个顶点共享一条边，则它们是相连的）。但是，我不清楚该怎么做。我发现有隐式图（由 returns 给定顶点的所有邻居的函数定义的图）。在这种情况下，这样的功能很容易实现。

问题是：我应该如何修改DFS算法来找到这种图中的组件？

Answer 1

当我们从一个顶点遍历边时，我们使用隐式边而不是存储边。
将顶点表示为它们的二维坐标很有用(row, col)。

伪代码可以如下：

dRow = [-1,  0, +1,  0]
dCol = [ 0, -1,  0, +1]
...later, when we want to move from vertex (row, col)...
for dir in [0..4):
    nRow = row + dRow[dir]
    nCol = col + dCol[dir]
    if vertex (nRow, nCol) is in rectangle bounds:
        try to move from vertex (row, col) to vertex (nRow, nCol)

这是在经典 DFS 实现中有一个循环的地方：

for each vertex u in {neighbors of vertex v}:
    try to move from vertex v to vertex u

如何在隐式图中找到多个连通分量？

How can I find a number of connected components in implicit graph?

algorithm

graph

implicit

depth-first-search

connected-components