Задача №112721. Вслепую по лабиринту
Это интерактивная задача. Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту. Лабиринт состоит из \(N\) на \(M\) (\(1 \le N, M \le 30\)) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместиться на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетку сработает сенсор и робот останется в той же клетке. Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.
Каждая строка входных данных представляет собой ответ на действие робота. Это может быть строка EMPTY если робот успешно переместился в заданном направлении или строка BLOCKED если робот не смог переместиться из-за того, что клетка, в которую он хотел попасть, непроходима.
Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: SOUTH, WEST, NORTH, EAST, или DONE. Строка DONE должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу. Необходимо очищать выходной буфер после вывода каждой команды (flush). Для этого используйте
* flush(output) в Паскале или Delphi; (не исключено, что writeln делает это сам)
* fflush(stdout) или cout.flush() в С/C++; (endl также это делает)
* stdout.flush() в Python (опять же, стандартный print может делать это сам)
Программа должна выводить на стандартный вывод одну строку с действием робота и ждать строки в стандартном вводе с ответом, затем выводить очередную строку с действием и считывать ответ и так далее до тех пор, пока все проходимые клетки лабиринта не будут посещены. Программа должна завершать работу только когда все проходимые клетки будут посещены. Проходимые клетки могут быть посещены несколько раз. Допустимо передвигаться даже если все проходимые клетки уже посещены.
##### #..o# ##..# #####
NORTH EAST SOUTH EAST SOUTH WEST SOUTH WEST NORTH WEST WEST NORTH EAST NORTH DONE