Задача 1. Лекция. Графы. Поиск в ширину

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

Кратчайшие пути

а.
б.
Рис 1. (а) Граф и (б) его дерево поиска в глубину.

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

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

а.
б.
Рис 2. (а) Граф и (б) его "подвешенный" за вершину S вид.

Например, на (рис. 2) расстояние между вершинами S и B равно 2, и есть два кратчайших пути между ними. Когда граф подвешен за S, все ребра этих двух путей натягиваются. А ребро (D, E) провисает, поскольку не входит ни в один из кратчайших путей из вершины S.

Поиск в ширину

Вершины графа рис. 2, подвешенного за S, разбиваются на слои: сама S, вершины на расстоянии 1 от S, вершины на расстоянии 2 и так далее. Можно находить расстояния от S до всех вершин, переходя от уровня к уровню. Когда вершины уровней 0, 1, 2, ..., d определены, легко найти вершины уровня d + 1: это просто еще не просмотренные вершины, смежные с вершинами уровня d. Эти рассуждения наталкивают нас на алгоритм, работающий в каждый момент с двумя уровнями: некоторым уровнем d, который уже полностью известен, и уровнем d + 1, который находится просмотром соседей вершин уровня d.

Для необходимого порядка просмотра вершин нам понадобится структура данных очередь. В такой структуре данных есть три операции:

Такую структуру данных легко реализовать с помощью массива (рис. 3).

procedure Push(v: integer);
begin
    q[qend] := v;
    qend += 1;
end;

function Pop(): integer;
begin
    Result := q[qbegin];
    qbegin += 1;
end;

function Empty(): boolean;
begin
    Result := (qbegin = qend);
end;
Рис. 3. Реализация очереди с помощью массива и пары индексов — начала и конца

Поиск в ширину (breadth-first search, BFS) непосредственно реализует вышеописанную идею обхода вершин (рис. 4). Изначально очередь Q содержит только вершину S, то есть вершину на расстоянии 0. Для каждого последующего расстояния d = 1, 2, 3, ... найдется момент времени, в который Q содержит все вершины на расстоянии d и только их. Когда все эти вершины будут обработаны (извлечены из очереди), их непросмотренные соседи окажутся добавленными в конец очереди, то есть мы перейдем к следующему значению d.

procedure bfs(start: integer);
var
    i, u, v: integer;
begin
    Push(start);

    used[start] := true;
    dist[start] := 0;

    while not Empty() do begin
        u = Pop();

        for i := 0 to High(adj[u]) do begin
            v = adj[u][i];

            if not used[v] then begin
                used[v] := true;
                Push(v);
                dist[v] := dist[u] + 1;
            end;
        end;
    end;
end;
Рис. 4. Реализация алгоритма поиска в ширину

Запустим этот алгоритм для вершины S в графе (рис. 1). Считаем, что соседи каждой вершины обрабатываются в алфавитном порядке. На (рис. 5) слева показан порядок обхода вершин, а справа изображено дерево поиска в ширину. Оно содержит только ребра, при переходе по которым обнаруживались новые вершины. В отличие от дерево поиска в глубину все пути данного дерева с началом в S являются кратчайшими. Поэтому оно называется деревом кратчайших путей (shortest-path tree).

Порядок обходаСодержание очереди
[S]
S[A~C~D~E]
A[C~D~E~B]
C[D~E~B]
D[E~B]
E[B]
S[]
а.
б.
Рис. 5. Результат поиска в ширину для графа рис. 1

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

Корректность и время работы

Убедимся в корректности алгоритма. Мы утверждаем, что для всех d = 0, 1, 2, ... найдется момент времени, когда:

  1. для всех вершин на расстоянии не более d это расстояние уже помещено в массив dist;
  2. для всех оставшихся вершин значения в dist равны (бесконечность);
  3. очередь содержит в точности вершины на расстоянии d.

Данное утверждение легко доказывается по индукции (проверьте).

Как и в случае поиска в глубину, время работы поиска в ширину линейно, то есть равно O(|V| + |E|). Действительно, каждая вершина помещается в очередь ровно один раз — при ее обнаружении. Поэтому общее количество операций с очередью есть 2|V|. Вся оставшаяся работы производится во внутреннем цикле алгоритма. На это требуется время O(|E|), поскольку каждое ребро в данном цикле просматривается один раз (для ориентированных графов) или два раза для неориентированных).

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

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

При поиске в ширину нас интересуют расстояния от s, поэтому мы не перезапускаем поиск в других связных компонентах (недоступные вершины просто игнорируются).

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2

Problem A. Breadth First Search

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives an unweighted undirected graph and writes all its vertices in order of increasing distance from given vertex S. Distance between vertices A and B is the length of the shortest path from A to B. If there are several vertices such that their distances to S are equal, they may be printed in arbitrary order.

Input file format

Input file contains three integers N, M and S, where M is the number of edges, S is the starting vertex. Vertices are numbered with integer numbers from 1 to N. Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.

Output file format

Output file must contain sequence of vertex numbers sorted by increasing distance from S. If some vertex is not reachable from S, output a single number 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2 1
1 2
2 3
1 2 3

Задача B. Лабиринт

Автор:Кленин А.   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

Формат входного файла

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

Формат выходного файла

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

1 ≤ N ≤ 1500, левый верхний угол лабиринта всегда свободен.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
.#
..
2
2
2
.#
#.
-1

Задача C. Суперагент

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Женя Борин учится в школе юных суперагентов. На занятии по избавлению от слежки Борин получил такое теоретическое задание:

Зал аэропорта на плане имеет вид прямоугольника шириной W и высотой H метров. Пол разделён на клетки размером 1 × 1 метр. Клетка в северо-западном углу имеет координаты (1, 1).

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

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

Агент находится в точке с координатами (1, ya) и желает попасть в точку с координатами (W, ya), не подняв тревоги и затратив не более T секунд. Требуется написать программу, которая определит необходимую последовательность перемещений агента по известным координатам и перемещениям пассажиров.

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

Формат входного файла

Первая строка входного файла содержит числа W H T ya N. Следующие N строк содержат значения xi yi pi, где xi, yi — координаты i-го пассажира в начальный момент времени, pi — строка из T символов, описывающая перемещения пассажиров в течении T секунд. Каждый символ равен "n", если пассажир перемещается на север, "s" — на юг, "w" — на запад, "e" — на восток, "z" — стоит на месте.

Формат выходного файла

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

Ограничения

1 ≤ W, H, T, N ≤ 100, ya и W — нечётные, 1 ≤ xi ≤ W, 1 ≤ yi, ya ≤ H

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 6 20 3 2
2 1 eeeeewwwwwweeeeeewww
3 2 ssssnnnnnsssssnnnnns
zzzzzzzzzzzeeeeee
2
3 4 5 3 1
1 1 zzzzz
IMPOSSIBLE

Задача D. Змейка

Автор:О. Бабушкин   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Подружки Катя и Надя уже давно играют в игру «Змейка».

Поле для игры представляет собой клетчатый квадрат со стороной n. В каждой клетке квадрата может быть либо зеленая лужайка, либо пень. Изначально в их распоряжении находится змейка длиной 1. За один шаг змейка может перемещаться в одном из 4х направлений: вверх, вниз, вправо и влево. Однако змейка не может ползать по пенькам.

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

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

Формат входного файла

В первой строке входного файла находится число n. В последующих n строках содержится по n символов задающих лабиринт. Лужайке соответствует символ ‘.’, пню – ‘#’, i-ому яблоку цифра i

Формат выходного файла

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

Ограничения

2 ≤ n ≤ 10.

2 ≤ k ≤ 8.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
#3.
1.2
#4#
        
6
2
3
#43
1.2
#5#
        
-1

0.081s 0.004s 25