Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Lines(2)#55126

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

Входные данные
В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. 2 <= N <= 250.

Выходные данные
В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но X, а также все точки по пути заменяются плюсами +.

Обход в ширину

✓ 2✗ 1—Войти и решать

Покраска лабиринта#55122

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

Входные данные
В первой строке находится число N, затем идут N строк по N символов: точка обозначает пустой сегмент, решётка - сегмент со стеной. 3 <= N <= 33, размер сегмента 3 x 3 м, высота стен 3 м.

Выходные данные
Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.

Обход в ширину

✓ 1✗ 1—Войти и решать

Lines#55121

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

Входные данные
В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика. 2 <= N <= 40.

Выходные данные
В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но буква X, а также все точки по пути заменяются плюсами.

Обход в ширину

✓ 2✗ 0—Войти и решать

Окопы и траншеи#55079

На полигоне, на котором проводятся военные учения сухопутных войск Флатландии, вырыты n окопов. Каждый окоп вырыт вдоль границы прямоугольника со сторонами, параллельными направлениям север–юг и запад–восток. При этом окопы могут иметь общие точки, но никакие два окопа не имеют общего участка ненулевой длины.

Очередные учения должны продемонстрировать способность солдат быстро и незаметно перемещаться из точки A в точку B.

Во время учений солдаты могут перемещаться либо по окопам, либо по траншеям, которые они могут прокапывать между окопами. При этом по окопам и выкопанным траншеям солдат может бегать настолько быстро, что временем перемещения от одной точки до другой можно пренебречь (будем считать его равным нулю). Траншеи же солдат копает со скоростью 1 метр в час.

Заданы точки A и B. Требуется определить, за какое минимальное время солдат во время учений сможет переместиться из А в B. Шириной траншей и окопов можно пренебречь.

Формат входных данных

Первая строка содержит число n — количество окопов на полигоне (1 ≤ n ≤ 500). Введем систему координат на полигоне таким образом, чтобы ось OX была ориентирована с запада на восток, а ось OY — с юга на север. Следующие n строк описывают окопы, каждый окоп описывается четырьмя целыми числами x₁, y₁, x₂, y₂ — координатами юго-западного и северо-восточного углов, соответственно (–10⁴ ≤ x₁ < x₁ ≤ 10⁴, –10⁴ ≤ y₁ < y₂ ≤ 10⁴).

Последние две строки содержат по два целых числа: x_A, y_A — координаты точки A и x_B, y_B — координаты точки B, соответственно (–10⁴ ≤ x_A, y_A, x_B, y_B ≤ 10⁴). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.

Формат выходных данных

Выведите одно вещественное число — количество часов, которое потребуется солдату, чтобы добраться из точки A до точки B. Ответ должен отличаться от правильного не более чем на 10^-6.

Алгоритм Дейкстры Вычислительная геометрия графы

✓ 1✗ 2—Войти и решать

Свет#54303

В точке (0, 0) координатной плоскости расположена лампочка, которая представляет собой точечный источник света. Неподалеку от лампочки находится дом Пети, который представляет собой выпуклый многоугольник с N вершинами. Сам Петя находится в точке с координатами (x, y).

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

Петя может перемещаться по плоскости со скоростью v. Разумеется, Петя не может проходить сквозь дом (хотя он может двигаться по его границе).

Выясните, какое минимальное время требуется Пете, чтобы оказаться в освещенной точке.

Входные данные
В первой строке вводятся координаты Пети – два неотрицательных вещественных числа, не превышающих 1000, и его скорость v – вещественное число, 10^-2≤ v≤ 10⁴.

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

Гарантируется, что входные данные корректны, в частности, многоугольник выпуклый, и никакие три его последовательные вершины не лежат на одной прямой. Также гарантируется, что и Петя, и лампочка находятся снаружи от многоугольника, в частности, не находятся на его границе. Расстояние от точки, где находится Петя, до многоугольника и от начала координат до многоугольника не меньше 10^-2, расстояние от Пети до начала координат не меньше 10^-2.

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

Алгоритм Дейкстры Элементарная геометрия

✓ 1✗ 0—Войти и решать

Военный поход#53989

В одном феодальном государстве средневековой Европы было \(n\) городов и \(m\) дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно одного из тех, которые она соединяла). Однажды правитель города S решил объявить войну правителю города T. Перед ним сразу же встала нелегкая задача: как довести армию до города T.

Правитель каждого города требует плату за проход войск через его город. Кроме того, правитель города S может перемещать войска только по дорогам, которые принадлежат ему. При этом он может купить любую дорогу у ее владельца за определенную плату (даже если владелец — правитель города T). К сожалению, все деньги из казны города S были потрачены на предыдущий неудачный военный поход, поэтому сначала правителю придется продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска).

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

Формат входных данных
Первая строка содержит целые числа \(n\) и \(m\) — количество городов и дорог соответственно (\(2 \le n \le 2\,000\), \(1 \le m \le 50\,000\)). Города нумеруются от 1 до \(n\), города S и T имеют номера 1 и \(n\) соответственно.

Следующие \(n\) строк содержат под одному целому числу \(r_i\) — плату за проезд через город \(i\) (\(0 \le r_i \le 10\,000\), \(r_1 = r_n = 0\)).

Следующие \(m\) строк содержат описания дорог. Дорога описывается четырьмя целыми числами: \(a_i\), \(b_i\), \(p_i\) и \(c_i\). Здесь \(a_i\) и \(b_i\) — номера городов, которые соединяет дорога, \(p_i\) — номер города, правителю которого она принадлежит, \(c_i\) — ее стоимость (\(a_i \ne b_i\), \(1 \le c_i \le 10\,000\)). По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более чем одной дорогой.

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

Если решения нет, выведите в выходной файл число \(-1\).

Алгоритм Дейкстры

✓ 1✗ 1—Войти и решать

В школу на велосипеде#53975

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

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

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

Входные данные
Будем считать, что в городе введена прямоугольная декартова система координат.

Первые две строки входных данных описывают велосипедные дорожки. Каждая из них содержит по три целых числа – координаты центра окружности, которую представляет собой соответствующая дорожка, и ее радиус. Координаты и радиус не превышают 200 по абсолютной величине, радиус – положительное число. Гарантируется, что дорожки не совпадают.

Следующие две строки содержат по два вещественных числа – координаты точки, где Петя заезжает на дорожку, и точки, в которой Петя съезжает с дорожки. Гарантируется, что каждая из точек с высокой точностью лежит на одной из дорожек (расстояние от точки до центра одной из окружностей отличается от ее радиуса не более, чем на 10^-8). Точки могут лежать как на одной дорожке, так и на разных.

Выходные данные
Выведите минимальное расстояние, которое следует проехать Пете по велосипедным дорожкам, чтобы попасть из дома в школу. Ответ должен отличаться от правильного не более, чем на 10^-4.

Если доехать из дома до школы по велосипедным дорожкам невозможно, выведите число -1.

Алгоритм Дейкстры Элементарная геометрия

✓ 1✗ 0—Войти и решать

Умывальники#53853

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

Так как Петя идёт умываться после отбоя, он смертельно боится попасться на глаза воспитателям ЛКШ. Однако, как выяснилось, в каждом коридоре стоит ровно по одному воспитателю, причём каждый из них считает своим долгом при встрече Пети влепить ему наряд вне очереди.

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

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

Входные данные
В первой строке входного файла четыре числа: N, S, V1, V2 (1 <= N <= 1000; 1 <= S, V1, V2 <= N), где N - общее количество холлов, S - номер холла, в котором Петя находится в начальный момент времени, V1, V2 - номера холлов, в которых располагаются умывальники. В следующих N строках по N чисел - 1 или 0. Стоящий в I-ой строке на J-ом месте 0 означает отсутствие коридора из I-го холла в J-ый, а стоящая 1 - присутствие.

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

Обход в ширину

✓ 20✗ 45700средняяВойти и решать

Нечестная игра#50448

На клетчатой доске размером \(n \times m\), состоящей из \(n\) строк и \(m\) столбцов, в клетке \((r, c)\), то есть на пересечении \(r\)-й сверху строки и \(c\)-го слева столбца, расположена фишка. На этой доске вам предстоит сыграть против компьютера в игру, в которой можно перемещать фишку и удалять клетки поля.

Каждый ход устроен следующим образом.

Компьютер называет целое число \(k > 0\).
Вы ровно \(k\) раз некоторым образом выбираете одну из еще не удаленных клеток, соседних по стороне (имеющих общую сторону) с той, в которой фишка находится в текущий момент, и перемещаете фишку в эту клетку. Вы можете перемещать фишку на клетку, в которой она уже была. Если не существует еще не удаленных клеток, соседних по стороне с текущей, перемещение не производится.
Компьютер называет координаты \((i, j)\) произвольной еще не удаленной клетки поля, после чего она сразу же удаляется.

Если компьютер удаляет клетку, на которой находится фишка, игра заканчивается вашей победой. Ваша цель — победить как можно раньше. При этом вы не сообщаете компьютеру свои перемещения, поэтому можете играть нечестно: вместо реального перемещения фишки по полю вы можете следить за всеми возможными ее положениями. Иными словами, если в какой-то момент при удалении клетки \((i, j)\) существует последовательность перемещений фишки, при которой в данный момент фишка находится в точности в клетке \((i, j)\), вы можете сообщить компьютеру, что игра завершена, и вы победили.

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

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

Формат входных данных
В единственной строке ввода даны четыре целых числа \(n\), \(m\), \(r\) и \(c\) — размеры доски и координаты изначального расположения фишки (\(1 \le r \le n \le 1000\); \(1 \le c \le m \le 1000\)).

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

В следующих \(n \cdot m\) строках даны ходы, которые последовательно собирается сделать компьютер. Описание \(t\)-го хода задается тремя целыми числами \(k_t\), \(i_t\) и \(j_t\) — количеством перемещений фишки, которые вам понадобится совершить, и координатами клетки поля, которую после этого требуется удалить (\(1 \le k_t \le 10^9\); \(1 \le i_t \le n\); \(1 \le j_t \le m\)).

Гарантируется, что все удаляемые клетки различны, то есть никакая клетка не удаляется дважды.

Формат выходных данных
Выведите одно целое число от \(1\) до \(n \cdot m\) — номер хода, после которого вы сообщите компьютеру о своей победе.

Замечание

В первом примере можно, например, первым ходом передвинуть фишку из \((1, 1)\) в \((1, 2)\), а вторым — из \((1, 2)\) в \((2, 2)\) и затем в \((2, 1)\), тем самым поместив ее на удаляемую клетку.

графы Задачи на моделирование Обход в ширину

✓ 4✗ 291 000средняяВойти и решать

Количество кратчайших путей#49684

В Сильвертауне есть N районов с номерами от 1 до N и M дорог с номерами от 1 до M. Используя дорогу i, вы можете добраться из района A_i в район B_i или наоборот за один час.
Сколько существует путей, по которым можно добраться из района 1 в район N как можно быстрее?
Поскольку число может быть огромным, выведите его по модулю 10⁹+7

Формат входных данных
Первая строка содержит два целых числа N и M. Далее идет M строк, в каждой из которых записано по 2 числа: A_i и B_i.

Ограничения

2 ≤ N ≤ 2×10⁵
0 ≤ M ≤ 2×10⁵
1 ≤ Ai < Bi ≤ N
Пары (Ai,Bi) уникальны.
Все значения во входных данных целые числа.

Формат выходных данных
Выведите ответ на задачу.

Обход в ширину

✓ 57✗ 155900средняяВойти и решать

Открыть все комнаты#49671

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

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

По известному набору заклинаний, определите сможет ли Максимум получить все артефакты или нет.

Формат входных данных
В первой строке записано число n (2 <= n <= 1000), количество комнат. Далее идет n строк. В i-й строке описываются заклинания, хранящиеся в этой комнате. В каждой из этих строк первое число (m, 0 <= m <= 1000) обозначает количество уникальных заклинаний, которые открывают комнаты, далее записаны m уникальных чисел rooms[i](0 <= rooms[i][j] < n) - номера комнат, которые открывают эти заклинания (0<=i<n, 1 <= общее количество заклинаний во всех комнатах <= 10000).

Формат выходных данных
Выведите True, если Максимус может посетить все комнаты и найти все магические артефакты, или False в противном случае.

Обход в ширину

✓ 75✗ 44700средняяВойти и решать

Ананасы на Шешинеру#38832

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

Алиса хочет хочет отправить как можно большее число ананасов. Капитан Полосков решил ей помочь и с радостью согласился слетать на своем космическом корабле. Но есть один нюанс: на некоторых космических маршрутах можно дозаправить корабль, не превышающий максимально установленный вес. А заправлять корабль в пути нужно всегда, иначе он просто не долетит. Поэтому если корабль заполнить ананасами по максимуму, то, его не получится дозаправить в пути и поэтому не удастся воспользоваться самым коротким маршрутов, и придётся лететь через другие планеты. Может случиться даже так, что корабль не успеет долететь до Шешинеры вовремя, и ананасы испортятся.
Итак, сколько же ананасов можно погрузить в космический корабль, чтобы доставить груз вовремя?

Входные данные
Программа получает на вход несколько строк. В первой строке находятся числа n (1 <= n <= 500) и m - количество планет и количество космических маршрутов между планетми, соответственно. В следующих m строках записана информация о маршрутах. Каждый маршрут описывается в отдельной строке следующим образом. Сначала указаны номера планет, которые соединяются космическим маршрутом, потом время, которое тратится на перелет по этому маршруту, и, наконец, максимальный космического корабля, который можно заправить на этом маршруте. Известно, что все космические маршруты соединяют различные планеты, причем для каждой пары планет есть не более одного маршрута, непосредственно их соединяющий. Все числа разделены одним или несколькими пробелами.

Планеты нумеруются числами от 1 до n. Планеты Земля имеет номер 1, а планета Шешинера - номер n. Время перелета по маршруту задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что один ананас весит 100 грамм, а пустой корабль - 3 тонны.

Выходные данные
Выведите одно число - максимальное количество ананасов, которое можно доставить, потратив не более 24часов.

Примеры

№	Входные данные	Выходные данные
1	3 3 1 2 10 3000220 2 3 20 3000201 1 3 1 3000099	2

Обход в ширину

✓ 2✗ 1—Войти и решать

Найти Дэйва#38831

Беззработный Дэйв от скуки соорудил в собственной гостиной лабиринт из картонных коробок. Лабиринт содержит K входов. Когда его подружка Энни вернулась, лабиринт невероятным образом разросся изнутри, а сам горе-изобретатель там заблудился и не может выбраться.
Единственное, что нашла Энни в комнате это карту лабиринта, который имеет размеры NхM клеток. На карте было обозначено место, в котором находится Дэйв (как так вышло никто не знает). Клетки лабиринта либо пустые, по которым можно пройти, либо в них находится стена и по ним проходить нельзя. У клетки может быть до 4-х смежных клеток, в которую можно пройти из текущей.
Энни пригласила вас помочь ей определить, с какого входа нужно начать свой путь, чтобы побыстрее дойти до Дейва. Если таких входов несколько, Энни пойдет со входа с наименьшим номером.

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

Программа получает на вход несколько строк. В первой строке - 2 числа N и M (1<= N, M <= 100, NxM <= 100), размеры лабиринта. Далее следует N строк по M символов в каждой - описание лабиринта. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с Дэйвом.
В (N+2)-й строке находится число K (1<=K<=NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. В i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1<=xi<=N,1<=yi<=M).
Координаты входов попарно различны, все входы расположены в пустых клетках. Ни один из входов не находится в клетке с Дэйвом.

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

Выведите одно число - номер входа (нумерация начинается с 1). Если до Дэйва невозможно добраться, выведите -1.

Примеры

№	Входные данные	Выходные данные
1	5 5 00000 00000 10*00 01111 00000 4 1 1 1 5 4 1 5 5	1
2	3 3 010 1*1 010 4 1 1 1 3 3 1 3 3	-1

Обход в ширину

✓ 13✗ 291 000средняяВойти и решать

Удаление клеток#38830

Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

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

В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.

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

Вывести одно число.

Примеры

№	Входные данные	Выходные данные
1	5 10 ##..#####. .#.#.#.... ###..##.#. ..##.....# .###.#####	5

Обход в глубину Обход в ширину

✓ 62✗ 170800средняяВойти и решать

Игрушечный лабиринт#38829

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

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

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

В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.

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

Выведите единственное число – минимальное количество наклонов, которые необходимо сделать, чтобы шарик покинул лабиринт через одно из отверстий.

Примеры

№	Входные данные	Выходные данные
1	4 5 0 0 0 0 1 0 1 1 0 2 0 2 1 0 0 0 0 1 0 0	3

Обход в ширину

✓ 5✗ 0—Войти и решать

BFS: Начало (Python)#38792

Некоторые деревни соединены между собой дорогами, которые можно представить в виде неориентированного графа. Вершины данного графа - это деревни, а ребра - дороги между деревнями (граф может содержать циклы). Известно, что в деревне S основана артель коробейников. Каждое утро, чтобы продать свою мелкую галантерею, коробейники выходят в деревни, которые еще не посетили, и в которые есть дорога из текущей. Артель коробейников всегда делится на группы так, чтобы они могли за один день обойти все деревни, которые имеют дороги из текущей.
За сколько дней коробейники посетят все деревни?
Напишите функцию \(bfs()\), которая будет возвращать ответ на задачу.

Входные данные
В первой строке вводятся 3 целых числа n, m, s (\(1 <= n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - количество деревень, количество дорог между ними и номер деревни, в которой основана артель коробейников. В следующих m строках содержится по 2 числа u, v(\(1 <= u, v <= n\)) - номера двух деревень, между которыми есть дорога. Индексация деревень ведется с 1.

Выходные данные
Выведите одно число - за сколько дней коробейники посетят все деревни.

Примеры

№	Входные данные	Выходные данные
1	6 7 1 1 2 1 5 2 3 5 4 3 4 3 6 4 6	4

Обход в ширину

✓ 727✗ 3 207600лёгкаяВойти и решать

Метро Давилона#38655

Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.

Входные данные
В первой строке задается два целых числа N (2<=N<=10⁵) и M (0<=M<=2*10⁵). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10⁶, pi ≠ qi.

Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите -1.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 3 1 2 1 2 3 1 3 1 2	1	Используйте линии компании 1: 1 → 2 → 3. Стоимость проезда 1 сантик.
2	8 11 1 3 1 1 4 2 2 3 1 2 5 1 3 4 3 3 6 3 3 7 3 4 8 4 5 6 1 6 7 5 7 8 5	2	Сначала используйте линии компании 1: 1 → 3 → 2 → 5 → 6. Затем используйте линии компании 5: 6 → 7 → 8. Стоимость проезда 2 сантика.
3	2 0	-1

Алгоритмы на графах Кратчайшие пути в графе

✓ 5✗ 651 000средняяВойти и решать

Два коня#38628

На стандартной шахматной доске (8х8) живут 2 шахматных коня: Красный и Зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у Зеленого коня День Рождения. Зеленый конь решил отпраздновать это событие вместе с Красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что Красный и Зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?

Входные данные
На вход программы поступают координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8), задающие столбец и строку соответственно).

Выходные данные
Требуется вывести наименьшее необходимое количество ходов, либо число -1, если кони не могут встретиться.

Примеры

№	Входные данные	Выходные данные
1	a1 a3	1

Обход в ширину

✓ 90✗ 110800средняяВойти и решать

Табличка#38625

Дана таблица, состоящая из N строк и M столбцов. В каждой клетке таблицы записано одно из чисел: 0 или 1. Расстоянием между клетками (x₁, y₁) и (x₂, y₂) назовем сумму |x1-x2|+|y1-y2|. Вам необходимо построить таблицу, в клетке (i, j) которой будет записано минимальное расстояние между клеткой (i, j) начальной таблицы и клеткой, в которой записана 1. Гарантируется, что хотя бы одна 1 в таблице есть.

Формат входных данных
В первой строке вводятся два натуральных числа N и M, не превосходящих 500. Далее идут N строк по M чисел - элементы таблицы.

Формат выходных данных
Требуется вывести N строк по M чисел - элементы искомой таблицы.

Обход в ширину

✓ 65✗ 67800средняяВойти и решать

Роботы#38573

В подземелье есть N залов, соединенных туннелями. В некоторых залах находятся роботы, которые одновременно получили команду собраться в одном месте.

Роботы устроены так, что, получив команду, они все начали двигаться с такой скоростью, что туннель между двумя любыми залами преодолевают за 1 минуту. Роботы не могут останавливаться (в том числе и в залах), а также менять направление движения, находясь в туннелях (однако попав в зал, робот может из него пойти по тому же туннелю, по которому он пришел в этот зал).

Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).

Входные данные
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.

Выходные данные
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 1 3 3 1 2 4	1
2	3 2 1 2 2 3 2 1 3	1

Задачи на моделирование Обход в ширину

✓ 2✗ 351 200средняяВойти и решать