Лабиринт представляет собой квадрат, состоящий из NxN сегментов. Каждый из сегментов может быть либо пустым, либо заполненным монолитной каменной стеной. Гарантируется, что левый верхний и правый нижний сегменты пусты. Лабиринт обнесён сверху, снизу, слева и справа стенами, оставляющими свободными только левый верхний и правый нижний углы. Директор лабиринта решил покрасить стены лабиринта, видимые изнутри (см. рисунок). Помогите ему рассчитать количество краски, необходимой для этого.
В первой строке находится число \(N\), затем идут \(N\) строк по \(N\) символов: точка обозначает пустой сегмент, решётка - сегмент со стеной. \(3 \leq N \leq 33\), размер сегмента 3 x 3 м, высота стен 3 м.
Вывести одно число - площадь видимой части внутренних стен лабиринта в квадратных метрах.
| Ввод | Вывод |
|---|---|
4 .... .... .... .... |
108 |
4 .... .##. .##. .... |
180 |
В неориентированном графе требуется найти длину минимального пути между двумя вершинами.
Первым на вход поступает число \(N\) – количество вершин в графе \((1 \leq N \leq 100)\). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.
Выведите \(L\) – длину кратчайшего пути (количество ребер, которые нужно пройти). Если пути не существует, выведите одно число -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 |
Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из \(N\) подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.
Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего из выходов. Вам, как специалисту по таким задачам, поручено рассчитать необходимое время для каждого из бункеров по заданному описанию помещения Сверхсекретной организации. Для вашего же удобства бункеры занумерованы числами от 1 до \(N\).
Сначала вводятся два натуральных числа \(N, K (1 \leq N \leq 100000, 1 \leq K \leq N)\) — количество бункеров и количество выходов соответственно.
Далее через пробел записаны \(K\) различных чисел от 1 до \(N\), обозначающих номера бункеров, в которых расположены выходы.
Потом идёт число \(M (1 \leq M \leq 100000)\) — количество туннелей. Далее вводятся \(M\) пар чисел – номера бункеров, соединенных туннелем. По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.
Выведите \(N\) чисел, разделенных пробелом — для каждого из бункеров минимальное время, необходимое чтобы добраться до выхода. Считайте, что время перемещения по одному туннелю равно 1.
| Ввод | Вывод |
|---|---|
3 1 2 3 1 2 3 1 2 3 |
1 0 1 |
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 |
В неориентированном графе требуется найти минимальный путь между двумя вершинами.
Первым на вход поступает число \(N\) – количество вершин в графе \((1 \leq N \leq 100)\). Затем записана матрица смежности (0 обозначает отсутствие ребра, 1 – наличие ребра). Далее задаются номера двух вершин – начальной и конечной.
Выведите сначала \(L\) – длину кратчайшего пути (количество ребер, которые нужно пройти), а потом сам путь. Если путь имеет длину 0, то его выводить не нужно, достаточно вывести длину.
Необходимо вывести путь (номера всех вершин в правильном порядке). Если пути нет, нужно вывести -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 |
На шахматной доске \(N \cdot N\) в клетке (\(x1, y1\)) стоит голодный шахматный конь. Он хочет попасть в клетку (\(x2, y2\)), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?
На вход программы поступает пять чисел: \(N, x1, y1, x2, y2 (5 \leq N \leq 20, 1 \leq x1, y1, x2, y2 \leq N)\). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - \((N, N)\).
В первой строке выведите единственное число \(K\) - наименьшее необходимое число ходов коня. В каждой из следующих \(K+1\) строк должно быть записано 2 числа - координаты очередной клетки в пути коня.
| Ввод | Вывод |
|---|---|
5 3 3 5 1 |
4 3 3 2 1 1 3 3 2 5 1 |
На стандартной шахматной доске (8х8) живут 2 шахматных коня: Красный и Зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у Зеленого коня День Рождения. Зеленый конь решил отпраздновать это событие вместе с Красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что Красный и Зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?
На вход программы поступают координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8), задающие столбец и строку соответственно).
Требуется вывести наименьшее необходимое количество ходов, либо число -1, если кони не могут встретиться.
| Ввод | Вывод |
|---|---|
a1 a3 |
1 |
Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. К сожалению, после вчерашнего употребления кефира, левая голова Змея соображает плохо. Поэтому Змей Горыныч может поворачивать направо и идти прямо, но не может поворачивать налево и разворачиваться на месте. Помогите Змею Горынычу определить длину кратчайшего пути до выхода из лабиринта.
В первой строке через пробел записаны числа \(r\) и \(c (4 \leq r, c \leq 20)\) - количество строк и столбцов в карте лабиринта. В каждой из следующих \(r\) строк записано по \(c\) символов, задающих эту карту. Символ \(S\) обозначает положение Змея Горыныча, символ \(F\) - точку выхода из лабиринта, символ \(X\) - стенку. Пробелами обозначены проходимые клетки. Гарантируется, что лабиринт окружен стенами. Перед началом движения Змей Горыныч может сориентироваться по любому из 4 направлений (вверх, вниз, влево или направо).
Выведите единственное число - расстояние, которое придется пройти Змею Горынычу. Гарантируется, что он всегда сможет выйти из лабиринта.
| Ввод | Вывод |
|---|---|
10 14 XXXXXXXXXXXXXX X XXX X XFXXXXX X XXX XX XX X X S X XX XXXXXX X X X X X X X X X X X XXX XX X XXXXXXXXXXXXXX |
29 |