print994. Игра

printИгра

Ограничения: время – 1s/2s, память – 8MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Одно время в среде охочих до игр комсомольцев была в ходу придуманная кем-то случайно игра. Проходит она на поле размером `N\ times\ N` (`4\ ≤\ N\ ≤\ 100`), в каждой клетке которого записано число от 1 до `N`.
Правила:
  • Игроки делают ходы по очереди.
  • Первым ходом первый игрок ставит фишку на одну из клеток самого левого столбца поля.
  • На втором и последующих ходах игроки могут двигать фишку вправо, вверх или вниз на количество позиций от 1 до числа, записанного в той клетке, на которой стоит фишка перед началом хода.
  • Фишка во время хода НЕ может проходить через уже пройденные клетки, то есть не может пересечь свою предыдущую траекторию. Также фишка не должна выходить за пределы игрового поля.
  • Игра заканчивается, как только фишка оказывается в крайнем правом столбце, при этом игрок, сделавший последний ход, выигрывает.
Спрашивается, какой игрок победит, если известна конфигурация игрового поля, и оба игрока играют оптимально.
Ввод
На первой строке входного файла – число `N`. Описание игрового поля содержится в последующих `N` строках, в каждой из которых находятся `N` чисел из отрезка `[1,N]`, разделенных пробелами.
Вывод
В выходном файле должно содержаться единственное число:
1 – если победит первый игрок
2 – если победит второй игрок

Пример ввода 1

4
1 2 2 2
1 1 1 1
1 2 1 1
1 1 2 1

Пример вывода 1

1

Пример ввода 2

4
2 2 1 2
1 2 1 2
2 2 2 1
2 1 2 2

Пример вывода 2

2
Источник: Турнир "Экспонента-2006"
loading