Задача №1975. Трусливые пешки
Задачи можно решать в любом порядке.
Сложность задач НЕ связана с их порядком.
Количество попыток сдачи не ограничено, но засчитываются только задачи, полностью прошедшие все тесты (статус "OK").
Дима и Катя играют в следующую игру: на доске 5x5 клеток установлено несколько трусливых пешек. Трусливая пешка – это фигура, для взятия которой не обязательно перемещаться на ее клетку, а достаточно просто создать для нее угрозу.
Игроки ходят по очереди. Первый ход делает Катя, у которой есть единственная ладья. За один ход можно поставить ладью в любую незанятую клетку шахматной доски. При этом все трусливые пешки, для которых создана угроза (то есть находящиеся на той же горизонтали или вертикали, что и ладья) – снимаются с доски. Обратите внимание, что трусливая пешка не защищает другую от угрозы. Следующий ход делает Дима. Он может поставить на доску одну новую трусливую пешку в любую незанятую и не находящуюся в данный момент под угрозой клетку. Затем снова ходит Катя и т.д.
Игра продолжается до наступления одного из событий:
1. Катя сделала N ходов и при этом на доске осталась хотя бы одна пешка – в этом случае выиграл Дима;
2. После некоторого хода Кати на доске не осталось ни одной пешки – в этом случае выигрывает Катя.
3. Кто-то из игроков не может сделать следующий ход. В этом случае присуждается ничья.
Определите, кто из игроков выиграет при правильной игре.
Сначала вводится 5 строк по 5 чисел в каждой – начальное расположение трусливых пешек на доске. Наличие пешки в какой-то клетке обозначается числом 1, отсутствие пешки – числом 0. Затем вводится число N (натуральное, не превышает 15) – максимально допустимое количество ходов Кати. Гарантируется, что Катя сможет сделать первый ход (изначально на доске есть хотя бы одна незанятая клетка).
Выведите число 1 – если выигрывает Катя; число 2 – если выигрывает Дима или число 3 – если игра заканчивается вничью.
Комментарий к примеру тестов
1. У Кати есть единственный способ сделать первый ход, после которого Дима сделать ход не может, так как все свободные клетки будут находиться под угрозой.
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
3
1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
3