Задача A. Политическая карта

Автор:И. Лудов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Недавно компьютерными археологами на одной из очень старых вычислительных машин, сохранившихся до наших дней, была обнаружена примитивная компьютерная игра — политико-экономическая стратегия. Для ее работы был необходим некогда мощный CGA адаптер с графическим режимом, позволяющим одновременно отображать четыре цвета. Как известно, этого количества достаточно для того, чтобы так раскрасить любую плоскую карту, разбитую на области, что из них любые две соседних получат разные цвета. В игре, о которой идет речь, отображение политической карты было основано именно на этом свойстве. Страны выглядели в виде четырехсвязных множеств пикселей одного цвета, причем две из них могли быть покрашены в один и тот же цвет. Но тогда они не должны были иметь общей границы (анклавов нет).

Археологам стало очень интересно, сколько же государств существовало на планете Земля в те отдаленные геологические эпохи, когда эта игра занимала умы множества несостоявшихся политиков каждый вечер. Кто знает, может тогда еще не прошло время феодальной раздробленности и их счет шел на тысячи... Чтобы удовлетворить свое любопытство, ученые сделали множество скриншотов, прокрутив карту на различные позиции, а потом склеили их. В результате получился двумерный массив пикселей, слишком большой, чтобы посчитать количество стран вручную. И как только эти древние люди могли держать в голове информацию о таком количестве игроков глобальной геополитики...

Теперь, чтобы дать окончательный ответ на интересующий археологов вопрос вам нужно написать программу, которая по данному массиву чисел определит в нем количество четырехсвязных областей.

Формат входного файла

Первая строка входного файла содержит числа W и H — ширину и высоту массива, соответственно.

Следующие H строк содержат по W целых чисел от 1 до 4 — цвета пикселей.

Формат выходного файла

В выходной файл выведите единственное целое число — количество стран на карте

Ограничения

1 ≤ W, H ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1
1 2 1 2
4
2
3 3
1 1 2
2 1 1
2 1 2
4

0.038s 0.008s 15