Навстречу друг другу
Дано прямоугольное клетчатое поле M × N клеток. Каждая клетка поля
покрашена в один из шести цветов, причем левая верхняя и правая нижняя
клетки имеют различный цвет. В результате поле разбивается на некоторое
количество одноцветных областей: две клетки одного цвета, имеющие общую
сторону, принадлежат одной области.
Правила игры
Играют два игрока. За первым игроком закреплена область, включающая левую
верхнюю клетку, за вторым – правую нижнюю. Игроки ходят по очереди.
Делая ход, игрок перекрашивает свою область:
А) в любой из шести цветов;
Б) в любой из шести цветов, за исключением цвета своей области и цвета
области противника.
В результате хода к области игрока присоединяются все прилегающие к ней
области выбранного цвета, если такие имеются. Если после очередного хода
окажется, что области игроков соприкасаются, то игра заканчивается.
Задание
Напишите программу, которая для каждого из пунктов (А и Б) определяет
минимально возможное число ходов, по прошествии которых игра может
завершиться.
Входные данные
Цвета пронумерованы цифрами от 1 до 6. Первая строка входного файла
содержит целые числа M и N – размеры поля (1 ≤ M,N ≤ 50). Далее следует
описание раскраски поля – M строк по N цифр (от 1 до 6) в каждой без
пробелов. Первая цифра файла соответствует цвету левой верхней клетки
игрового поля. Количество одноцветных областей не превосходит 50.
Выходные данные
В выходной файл выведите искомое количество ходов для каждого из пунктов.
Пример входного файла
4 3
122
221
143
132
Пример выходного файла
3
4