Страница: << 35 36 37 38 39 40 41 >> Отображать по:

#2867

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

Темы: [Интерактивные задачи] [Обход в глубину]

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

Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту.

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

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

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

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

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

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

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

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

Примеры

Входные данные	Выходные данные
NORTH EAST SOUTH EAST SOUTH WEST SOUTH WEST NORTH WEST WEST NORTH EAST NORTH DONE	BLOCKED BLOCKED EMPTY BLOCKED BLOCKED EMPTY BLOCKED BLOCKED EMPTY EMPTY BLOCKED BLOCKED EMPTY BLOCKED

#2868

Дерево?

Темы: [Обход в глубину]

Имеется неориентированный граф, состоящий из N вершин и M ребер. Необходимо проверить, является ли граф деревом. Напомним, что дерево — это связный граф, в котором нет циклов (следовательно, между любой парой вершин существует ровно один простой путь). Граф называется связным, если от одной вершины существует путь до любой другой.

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

Во входном файле в первой строке содержатся два целых числа N и M (1 ≤ N ≤ 100, 0 ≤ M ≤ 1000), записанные через пробел. Далее следуют M различных строк с описаниями ребер, каждая из которых содержит два натуральных числа Ai и Bi (1 ≤ Ai <Bi ≤ N), где Ai и Bi — номера вершин, соединенных i-м ребром.

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

В выходной файл выведите слово YES, если граф является деревом или NO в противном случае.

Примеры

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

3 2
1 2
1 3

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

YES

#2871

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

Темы: [Интерактивные задачи] [Обход в глубину]

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

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

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

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

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

Пример

Выходные данные	Входные данные
NORTH EAST SOUTH EAST SOUTH WEST SOUTH WEST NORTH WEST WEST NORTH EAST NORTH DONE	BLOCKED BLOCKED EMPTY BLOCKED BLOCKED EMPTY BLOCKED BLOCKED EMPTY EMPTY BLOCKED BLOCKED EMPTY BLOCKED

#2872

Дерево?

Темы: [Обход в глубину]

Имеется неориентированный граф, состоящий из \(N\) вершин и \(M\) ребер. Необходимо проверить, является ли граф деревом. Напомним, что дерево — это связный граф, в котором нет циклов (следовательно, между любой парой вершин существует ровно один простой путь). Граф называется связным, если от одной вершины существует путь до любой другой.

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

Во входном файле в первой строке содержатся два целых числа \(N\) и \(M\) (\(1 \le N \le 100\), \(0 \le M \le 1\,000\)), записанные через пробел. Далее следуют \(M\) различных строк с описаниями ребер, каждая из которых содержит два натуральных числа \(A_i\) и \(B_i\) (\(1 \le A_i < B_i \le N\)), где \(A_i\) и \(B_i\) — номера вершин, соединенных \(i\)-м ребром.

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

В выходной файл выведите слово «YES», если граф является деревом, или «NO» в противном случае.

Примеры

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

3 2
1 2
1 3

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

YES

#2885

Пульт дистанционного управления

Темы: [Обход в ширину] [Способы задания графа]

Страница: << 35 36 37 38 39 40 41 >> Отображать по:

Выбрано

Отменить

Добавить в контест