Звезды за кормой

В последнее время Петя очень заинтересовался одной игрой. Вкратце правила таковы: Имеется море размером (2•n+1) x (2•n+1) клеток. Изначально в некоторых клетках находятся острова, в некоторых – вражеские корабли, в центре стоит корабль игрока. За один ход игрок может либо переместиться, либо выстрелить; пропустить ход нельзя.

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

При выстреле корабль производит залп обоими бортами. Ядра при этом летят перпендикулярно текущему курсу корабля. Ядра каждого борта поражают первую встретившуюся в данном направлении цель (корабль или остров), но не далее трех клеток от корабля игрока (не считая клетку, на которой находится сам корабль игрока). Например, если корабль приплыл из клетки (2, 1) в клетку (1, 2), а затем выстрелил, то он уничтожит вражеский корабль на клетке (4, 5), но не поразит корабль на (5, 6). Если к тому же на клетке (2, 3) будет стоять корабль или остров, то корабль на (4, 5) останется цел. Изначально корабль игрока стоит на клетке (n, n) с таким направлением, будто он приплыл из клетки (n−1, n).

После каждого хода игрока вражеские корабли одновременно делают ход. Каждый из кораблей ходит на ту из восьми соседних клеток, сумма модулей разностей координат которой и координат корабля игрока минимальна. Формально, если корабль игрока находится на клетке (x_s, y_s), то выбирается такая клетка (x, y), для которой |x_s−x|+|y_s−y| минимально. Если при этом оказывается, что в данной клетке находится остров, то вражеский корабль погибает. Если хотя бы один вражеский корабль попадает на клетку с кораблем игрока, то игрок проигрывает. Если хотя бы два вражеских корабля оказываются на одной клетке, то они погибают и на этой клетке образуются обломки, которые далее действуют так же, как остров за тем исключением, что снаряды перелетают через обломки, а не поражают их. При уничтожении корабля ядром тоже образуются обломки. На месте острова обломки не образуются. Игрок побеждает, если на поле нет ни одного живого вражеского корабля.

Пете стало очень интересно, можно ли в каждой конкретной ситуации выиграть или нет. Для этого он решил написать программу. Нет, Вам не надо ему помогать. Он с этой задачей уже справился, а вот справитесь ли вы?

Входные данные

В первой строке входного файла INPUT.TXT задано число n (1 ≤ n ≤ 6), определяющее размер поля. Далее следуют 2•n+1 строк по 2•n+1 символов в каждой. При этом i-й символ (j+1)-й строки описывает клетку поля с координатами (i−1, j−1) (клетки нумеруются с 0). Значение символов следующее:

• «.» (точка) – пустая клетка;
• «t» (t маленькое английское) – вражеский корабль;
• «O» (o большое английское) – остров;
• «+» (плюс) – корабль игрока.

Символ «+» всегда присутствует и располагается только в клетке с координатами (n×n). Количество остальных символов может быть любым, и ограничено только размерами доски.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите количество ходов, необходимых для выигрыша. В последующих строках выведите координаты корабля после каждого из ходов, по одной паре в строке. Минимизировать число ходов не обязательно; тем не менее, если вражеских кораблей уже не осталось, дальнейшие ходы делать не следует. Если решения не существует, выведите IMPOSSIBLE в единственной строке файла. Если существует несколько решений, выведите любое.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]