Олимпиада проводится при поддержке Московского физико-технического института, Компьютерной компании НИКС, Компании Yandex
Информационная поддержка:
журнал "Мир ПК"
IV Открытая олимпиада школьников по программированию, 2009/10 учебный год
Задача L. Заливка
| Имя входного файла: | l.in |
| Имя выходного файла: | l.out |
| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
Вася - начинающий программист. Последней его идеей было написать графический редактор черно-белых изображений. К сожалению, вдохновения хватило только на один инструмент - заливку.
В окне редактора картинка отображается как прямоугольная таблица M x N клеток; каждая покрашена либо в чёрный, либо в белый цвет. Две клетки назовём соседними, если у них имеется общая сторона. Областью же будем называть максимальное подмножество клеток одного цвета, такое, что из каждой можно попасть в каждую, перемещаясь только по соседним клеткам этой области.
Заливка работает следующим образом: пользователь указывает на произвольную клетку таблицы, после чего вся область, содержащая данную клетку, перекрашивается в противоположный цвет.
Теперь Вася хочет научиться стирать изображения с помощью своего редактора. Картинка считается чистой, если она либо полностью чёрная, либо полностью белая. Определите минимальное число заливок, которое потребуется для того, чтобы сделать из данного изображения чистое.
Формат входных данных
Вводятся два натуральных числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) - количество строк и столбцов у таблицы, соответствующей данному изображению. В следующих N строках содержатся по M символов. В i й строке и j-м столбце стоит 0, если соответствующая клетка белая, и 1, если чёрная.
Формат выходных данных
Выведите одно число - минимальное количество заливок, требуемых для стирания данной картинки.
Пример
| l.in | l.out |
3 5 10101 01010 10101 |
3 |