Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Вслепую по лабиринту

(Время: 1 сек. Память: 16 Мб Сложность: 53%)

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

Ваша цель – написать программу, управляющую роботом, который движется вслепую по лабиринту. Лабиринт состоит из N на M (3 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в некоторой свободной клетке, он может переместиться на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетку сработает сенсор и робот останется в той же клетке.

Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.

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

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

Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: «SOUTH», «WEST», «NORTH», «EAST», или «DONE». Строка «DONE» должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу.

Каждая строка входных данных представляет собой ответ на действие робота. Это может быть строка «EMPTY», если робот успешно переместился в заданном направлении или строка «BLOCKED», если робот не смог переместиться из-за того, что клетка, в которую он хотел попасть, непроходима.

Пример

стандартный вводстандартный вывод
1BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
NORTH
EAST
SOUTH
EAST
SOUTH
WEST
SOUTH
WEST
NORTH
WEST
WEST
NORTH
EAST
NORTH
DONE

Примечание

Для корректной работы программы после каждой операции вывода данных вам необходимо делать переход на новую строку и очищать буфер вывода, то есть делать следующие операции:

  • В языке Pascal: flush(output)
  • В С/С++: fflush(stdout) или cout.flush()
  • В Java: System.out.flush()
  • В Python: sys.stdout.flush() из библиотеки sys
  • В C# и Basic: Console.Out.Flush()

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2007 / 2008 1 тур
 2007 / 2008 2 тур
 2007 / 2008 3 тур
 2008 / 2009 1 тур
 2008 / 2009 2 тур
 2008 / 2009 3 тур
 2009 / 2010 1 тур
 2009 / 2010 2 тур
 2009 / 2010 3 тур
 2010 / 2011 1 тур
 2010 / 2011 2 тур
 2010 / 2011 3 тур
 2011 / 2012 1 тур
 2011 / 2012 2 тур
 2011 / 2012 3 тур
 2012 / 2013 1 тур
 2012 / 2013 2 тур
 2012 / 2013 3 тур
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 A. Конфеты
 B. Счёт
 C. Слова-анаграммы
 D. Вслепую по лабиринту

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru