Страница: 1 [Всего задач: 2]      

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

Правила игры
Играют два игрока. За первым игроком закреплена область, включающая левую верхнюю клетку, за вторым – правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекрашивает свою область: 
    А) в любой из шести цветов;
    Б) в любой из шести цветов, за исключением цвета своей области и цвета области противника.
В результате хода к области игрока присоединяются все прилегающие к ней области выбранного цвета, если такие имеются. Если после очередного хода окажется, что области игроков соприкасаются, то игра заканчивается.

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

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

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

Пример входного файла
4 3
122
221
143
132

Пример выходного файла
3
4

Прислать комментарий

Решение

Для игры «Отравленный пирог» используется прямоугольный пирог, разделенный на M «строк» горизонтальными разрезами и на N «столбцов» – вертикальными. Таким образом, пирог должен быть разбит на M × N клеток, правая нижняя из которых «отравлена». Играют двое игроков, ходы делаются по очереди. Каждый ход заключается в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает все клетки, расположенные левее и выше выбранной (в том числе и выбранную). Проигрывает тот, кто съедает отравленную клетку.

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

Входные данные
Данные во входном файле расположены в следующем порядке: M, N (1 ≤ M, N ≤ 9), X₁, ..., X_M. Здесь X_i – число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами и/или символами перевода строки.

Выходные данные
В первую строку выходного файла необходимо вывести количество различных выигрышных ходов К, а в последующие K строк – сами выигрышные ходы.

Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального ряда, а j – номер (справа) вертикального ряда, которому принадлежит выбранная клетка (1 ≤ i ≤ M, 1 ≤ j ≤ N).

Пример входного файла
3 5
5 4 3

Пример выходного файла
1
3 1

Прислать комментарий

Решение

Страница: 1 [Всего задач: 2]