Задача №1976. Короли-захватчики
Ограничение по времени: 4 секунды
Андрей и Антон играют в следующую игру: на прямоугольную доску размера MxN, некоторые клетки в которой заняты "нейтральными" фигурами, игроки по очереди выставляют белых и черных шахматных королей (ход можно делать только в свободные клетки). Двигать или убирать уже поставленного короля нельзя. Убирать или перемещать "нейтральные" фигуры нельзя. Также нельзя ставить короля в клетку, которая является соседней с королем противника по горизонтали, вертикали или диагонали. Проигрывает тот, кто не сможет сделать следующий ход.
Определите, кто выиграет при правильной игре.
Вводятся числа M и N (натуральные, не превышают 5). Затем вводится число k – количество "нейтральных" фигур на доске (целое, положительное, не превышает количества клеток доски). Затем следует k строк по 2 числа в каждой – номера строки и столбца, где находится данная "нейтральная" фигура. Гарантируется, что хотя бы первый игрок сможет сделать первый ход (не вся доска покрыта "нейтральными" фигурами).
Выведите число 1, если выигрывает игрок, ходящий первым; выведите число 2, если выигрывает игрок, ходящий вторым.
1 2 0
1
1 3 1 1 2
2