Подсчет количества групп в матрице

Я нашел интересную проблему.

Дана матрица n*m в такой форме:

11111111
11111001
11111001
10111111
10111111
11100111
11111111

Цель задачи - найти количество блоков "0". В предыдущем примере было 3 блока "0".

Я не понимаю, как решить эту проблему. Я не прошу какой-либо код, я хотел бы получить некоторые советы о том, как решить эту проблему.

Источник

2 ответа

Решение

Вы можете использовать поиск в глубину, чтобы найти связанные компоненты в графе, где вершины - это ячейки с 0, а ребро между двумя вершинами присутствует, если две ячейки смежны.

Источник

Учитывая ваше определение блока: Для каждой строки вы проверяете, есть ли два (или более) смежных нуля, если это так, вы увеличиваете количество блоков 0 на 1 для каждого из этих вхождений.

Вы повторяете ту же процедуру для столбцов матрицы.

Я не уверен из вашего описания проблемы, как вы должны считать большие блоки, как:

1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1

Это один блок?

Источник
Другие вопросы по тегам