Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Обход в ширину

Условие задачи  
ID 22020: Путь
Путь
Темы: Обход в ширину   

В неориентированном графе требуется найти минимальный путь между двумя вершинами. 
 
Входные данные: В первой строке записано число N - количество вершин в графе (1<=N<=100). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем с новой строки записаны номера двух вершин - начальной и конечной.
 
Выходные данные: В выходной файл выведите сначала L - длину пути (количество ребер, которые нужно пройти). А затем выведите L+1 число - вершины в порядке следования вдоль этого пути. Если пути не существует, выведите одно число -1.

Примеры
Входные данные Выходные данные
1
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
3
3 2 1 5

ID 33251: Один конь
Один конь
Темы: Обход в ширину   

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?
 
Входные данные: На вход программы поступает  пять чисел: N, x1, y1, x2, y2 (5 <= N <= 20, 1 <= x1, y1, x2, y2 <= N). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).
 
Выходные данные: Выведите единственное число K - наименьшее необходимое число ходов коня. 

Примеры
Входные данные Выходные данные
1 5
1 1
3 2
1

ID 34976: Эвакуация
Эвакуация
Темы: Обход в ширину   

Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из N подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.

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

Входные данные: Сначала вводятся два натуральных числа N, K (1 ≤ N ≤ 100000, 1 ≤ K ≤ N) — количество бункеров и количество выходов соответственно.
Далее через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы.
Потом идёт число M (1 ≤ M ≤ 100000) — количество туннелей. Далее вводятся M пар чисел – номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.

Выходные данные: Выведите N чисел, разделенных пробелом — для каждого из бункеров минимальное время, необходимое чтобы добраться до выхода. Считайте, что время перемещения по одному туннелю равно 1.

Примеры

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

3
1 2
3 1
2 3
1 0 1
2 10
2
10 8 
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2
1 4 1 2 1 3 2 0 3 0

ID 19885: Длина пути
Длина пути
Темы: Обход в ширину    Очередь   

В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.
 
Входные данные: В первой строке входных данных записано сначала число N - количество вершин в графе (1<=N<=100). Затем с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). Затем с новой строки записаны номера двух вершин - начальной и конечной.
 
Выходные данные: Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.

Примеры
Входные данные Выходные данные
1
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
3

ID 37016: Преобразуем четырехзначные
Преобразуем четырехзначные
Темы: Обход в ширину   

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

1. Можно увеличить первую цифру числа на 1, если она не равна 9.
2. Можно уменьшить последнюю цифру на 1, если она не равна 1.
3. Можно циклически сдвинуть все цифры на одну вправо.
4. Можно циклически сдвинуть все цифры на одну влево.

Например, применяя эти правила к числу 1234 можно получить числа 2234, 1233, 4123 и 2341 соответственно. Точные правила игры Витя пока не придумал, но пока его интересует вопрос, как получить из одного числа другое за минимальное количество операций.


Входные данные: на вход подаются два различных четырехзначных числа, каждое из которых не содержит нулей. Каждое число с новой строки

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

Примеры
Входные данные Выходные данные
1 1234
4321
1234
2234
3234
4323
4322
4321