Картинка задана матрицей цифр — «пикселей». Одинаковые соседние цифры образуют
фигуры: например, единицы — квадрат, двойки — столбик, тройка — точку.
Заливка (как в Paint) закрашивает одну связную область пикселей одного цвета;
соседями считаются клетки, касающиеся сторонами (не по диагонали).
Посчитайте, за сколько заливок можно закрасить всю картинку, то есть сколько
в ней связных одноцветных областей.
// CountFills возвращает число одноцветных связных областей картинки.
func CountFills(img [][]int) int
Примеры
1 1 2 3
1 1 2 0 → 5 (квадрат из 1, столбик из 2, точка 3,
0 0 2 0 две несвязанные области нулей)
7 7 7
7 7 7 → 1
1 2
2 1 → 4 (диагональ не соединяет)
Ограничения
- Картинка прямоугольная,
0 ≤ M, N, M·N ≤ 4·10⁶, цвета — любые int.
- Картинку менять нельзя.
- Ожидается O(M·N). Учтите, что одна область может занимать всю картинку и
иметь форму длинной змейки.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.