eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Термінатор

Термінатор

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Два гровці грають у настільну гру. Ігрове поле являє собою квадратний лабіринт, 8×8 клітинок. У деяких клітинках розміщуються стінки. Один гравець керує фішкою-термінатором, а другий – фішкою-утікачем. Гравці ходять по черзі, ходи пропускати не можна (гарантується, що хід завжди можливий). За один хід гравець може перемістити свою фішку у довільну з вільних клітинок, розміщених поряд з заданою по горизонталі, вертикалі чи по діагоналі (тобто ходом короля). Термінатор, кріме того, может стріляти у втікача ракетами. Постріл йде по прямій у довільному напрямку по горизонталі, вертикалі чи діагоналі. Якщо утікач опиняється на лінії пострілу термінатора і не прикритий стінками, то термінатор миттєво робить постріл (не залежно від того, чий хід), і утікач програє. Початкове положення фішок задано. Перший хід робить утікач. Він вииграє, якщо зробить хід з восьмого рядка за межі ігрового поля, так як інші границі поля оточено стінками.

Питання задачі: чи може утікач виграти при оптимальній грі обох сторін?

Вхідні дані

У вхідному файлі задано ігрове поле. Вільну клітику позначено цифрою 0, а клітинку зі стінкою – цифрою 1. Клітинку, у якій знаходиться утікач, позначено цифрою 2, а клітинку з термінатором – цифрою 3.

Вихідні дані

У вихідний файл виведіть число 1, якщо утікач виграє, і -1 – у протилежному випадку.

Приклад

Вхідні дані #1
01000000
10100000
31100000
00020000
00000000
00000000
00000000
00000000
Вихідні дані #1
-1
Джерело Orel STU & Udmurt SU Contest, Petrozavodsk, Thursday, September 1, 2005