Задача по программированию

Дано прямоугольное клетчатое поле M × N клеток. Каждая клетка поля покрашена в один из шести цветов, причем левая верхняя и правая нижняя клетки имеют различный цвет. В результате поле разбивается на некоторое количество одноцветных областей: две клетки одного цвета, имеющие общую сторону, принадлежат одной области.

Правила игры

Играют два игрока. За первым игроком закреплена область, включающая левую верхнюю клетку, за вторым – правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекрашивает свою область:

А) в любой из шести цветов;

Б) в любой из шести цветов, за исключением цвета своей области и цвета области противника.

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

Задание

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

Входные данные

Цвета пронумерованы цифрами от 1 до 6. Первая строка входного файла (input.txt) содержит целые числа M и N – размеры поля (1 ≤ M,N ≤ 50). Далее следует описание раскраски поля – M строк по N цифр (от 1 до 6) в каждой без пробелов. Первая цифра файла соответствует цвету левой верхней клетки игрового поля. Количество одноцветных областей не превосходит 50.

Выходные данные

В выходной файл(output.txt) выведите искомое количество ходов для каждого из пунктов.

Примечание. Программу надо сделать в visual studio, в windows form. Язык C#