Как я могу найти несколько связанных компонентов в неявном графе?

Question

У меня есть проблема CS, которая сформулирована так:

Учитывая лист бумаги с вырезанными ячейками, представленными символами (либо "." (Вырезано), либо "#" (не вырезано)), мне нужно найти, сколько кусков будет сформировано.

Пример:

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

Ответ для примера выше 5.

Одна часть сформирует:

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

Две части сформируют:

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

Здравый смысл подсказывает мне найти способ представления листа с помощью графа (каждый числовой знак является вершиной, и две вершины связаны, если они имеют общую сторону). Однако мне неясно, как это сделать. Я обнаружил, что существуют неявные графы (графы, определенные функцией, которая возвращает всех соседей данной вершины). Подобную функцию тривиально реализовать в данном случае.

Вопрос в том, как мне изменить алгоритм DFS, чтобы найти компоненты в этом виде графика.

Answer 1

1. Когда мы зацикливаем ребра из вершины, мы используем неявные ребра вместо сохраненных ребер.

2. Полезно представлять вершины в виде их двумерных координат. (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