408277: GYM103075 J Рудольф и марсоход

J. Рудольф и марсоходограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

Это интерактивная задача.

Рудольф является разработчиком новейшего марсохода, который отправится на Марс для изучения его ледовых покровов.

Ледовый шельф представляет собой квадратную область размера $$$N \times N$$$, разделённую на участки $$$1 \times 1$$$. Участки нумеруются по горизонтали числами от $$$0$$$ до $$$(N - 1)$$$ с запада на восток, по вертикали — числами от $$$0$$$ до $$$(N - 1)$$$ с севера на юг. Таким образом, участок в северо-восточном углу шельфа имеет координаты $$$(N - 1; 0)$$$, а в юго-западном — $$$(0; N - 1)$$$.

Некоторые из участков могут содержать ледяные разломы. Миссия марсохода — составить карту этих разломов на всём шельфе.

Марсоход будет спущен на шельф в участке с координатами $$$(X_S; Y_S)$$$. Он должен исследовать местность, а затем добраться до участка с координатами $$$(X_E; Y_E)$$$ для эвакуации. Стартовый и конечный участки не содержат разломов, от стартового участка марсоход может добраться до конечного, а также до всех участков с разломами, перемещаясь по участкам, соседним по стороне.

Марсоход может выполнять следующие команды перемещения:

• $$$\texttt{1 K}$$$ — переместиться на $$$K$$$ участков севернее;
• $$$\texttt{2 K}$$$ — переместиться на $$$K$$$ участков восточнее;
• $$$\texttt{3 K}$$$ — переместиться на $$$K$$$ участков южнее;
• $$$\texttt{4 K}$$$ — переместиться на $$$K$$$ участков западнее.

  Марсоход не может выезжать за границы шельфа или заезжать на участки с ледяными разломами. В ответ на любую корректную команду перемещения марсоход возвращает сообщение $$$\texttt{OK}$$$. Некорректная команда перемещения приведёт к провалу миссии.

Кроме команд перемещения, марсоход может выполнять команды анализа местности:

• $$$\texttt{10}$$$ — узнать количество ледяных разломов на участках, соседних по стороне или углу с тем участком, в котором сейчас находится марсоход.

  В ответ на команду $$$\texttt{10}$$$ марсоход возвращает целое число от $$$0$$$ до $$$8$$$;

• $$$\texttt{100 X Y}$$$ — узнать количество ледяных разломов на участках, соседних по стороне или углу с участком, имеющим координаты $$$(X; Y)$$$. Сам этот участок обязан быть соседним по стороне с тем участком, в котором сейчас находится марсоход.

  Эта команда требует запроса к орбитальной станции, поэтому выполнять её марсоход может только в том случае, если, во-первых, он ещё не выяснил расположение всех разломов, и, во-вторых, он не может безопасно проехать ни по одному участку, на которых он ещё не побывал.

  В ответ на корректную команду $$$\texttt{100}$$$ марсоход возвращает целое число от $$$\texttt{0}$$$ до $$$\texttt{8}$$$, либо сообщение $$$\texttt{DANGER}$$$, если сам участок с координатами $$$(X; Y)$$$ содержит разлом. Некорректная команда $$$\texttt{100}$$$ приведёт к провалу миссии.

Наконец, когда марсоход завершит свою работу и будет готов к эвакуации, он должен выполнить последнюю команду:

• $$$\texttt{0}$$$ — завершить миссию. После этой команды следует вывести $$$N$$$ строк, каждая из которых содержит по $$$N$$$ символов $$$\texttt{.}$$$ или $$$\texttt{*}$$$ — карту шельфа. Символы $$$\texttt{.}$$$ должны соответствовать участкам без разломов, $$$\texttt{*}$$$ — участкам с разломами.

В настоящее время марсоход тестируют на испытательном полигоне. Помогите Рудольфу управлять его творением!

Протокол взаимодействия

Первая строка стандартного потока ввода содержит целое число $$$N$$$ ($$$1 \le N \le 10$$$) — размер ледового шельфа.

Вторая строка стандартного потока ввода содержит четыре целых числа $$$X_S$$$, $$$Y_S$$$, $$$X_E$$$, $$$Y_E$$$ ($$$0 \le X_S, Y_S, X_E, Y_E \le N - 1$$$) — соответственно координаты участков старта и эвакуации.

После считывания данных строк ваша программа должна выводить в стандартный поток вывода команды для марсохода в описанном выше формате. После каждой команды следует выводить символ перевода строки и сбрасывать буфер вывода:

• $$$\texttt{fflush(stdout)}$$$ в C++;
• $$$\texttt{System.out.flush()}$$$ в Java;
• $$$\texttt{stdout.flush()}$$$ в Python.

Если будет выведена некорректная команда, решение получит вердикт «Неправильный ответ». Если команда не будет выведена или не будет сброшен буфер вывода, решение получит вердикт «Решение зависло».

После вывода команды, отличной от команды $$$\texttt{0}$$$, программа должна считать из стандартного потока ввода ответ марсохода в описанном выше формате.

После вывода команды $$$\texttt{0}$$$ программа должна завершить работу.

ПримерВходные данные

3
0 0 2 2
0
OK
0
OK
1
OK
OK
0
OK
0
OK

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

10
3 1
10
2 1
10
4 1
3 1
10
2 1
10
2 1
0
..*
...
...