Эпидемия гриппа не обошла стороной семиклассника Алешу. Скучая дома, Алеша решил вырезать фигурки из листа клетчатой бумаги. Лист состоял из M строк и N столбцов клеточек. Сначала Алеша нарисовал на листе границы фигур. Количество фигур было не меньше 2. Чтобы фигуры получались ровными, границы фигур Алеша рисовал строго по линиям имеющейся клеточной разметки листа (при этом некоторые границы фигур могли пройти по границам листа). Форма фигур могла быть любой, но при этом все фигуры были связными (фигура называется связной, если из любой ее клетки можно добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4-х соседних по стороне клеток). Никакие две фигуры не имели общих точек, в том числе не касались углами клеток.
<>Затем Алеша вырезал нарисованные фигуры, делая разрезы только по их границам. При этом оставшаяся часть листа осталась связной (то есть не распалась на несколько частей).Лист с вырезами Алеша отсканировал. Сканер в своей памяти по результатам сканирования построил таблицу, состоящую из нулей и единиц, из M строк и N столбцов (строки нумеруются сверху вниз от 1 до M, столбцы — слева направо от 1 до N). Каждый элемент таблицы соответствовал клеточке исходного листа. Единица обозначала, что соответствующая клетка листа осталась на месте, ноль — соответствующая клетка была вырезана.
На рис. 1 приведен пример клетчатого листа, а на рис. 2 — соответствующая ему таблица в памяти сканера:
|
Рис 1. Исходный клеточный лист с вырезанными фигурами Размер листа: M=6, N=12. Количество вырезанных фигур: 3
|
Рис 2. Такая таблица строится в памяти сканера
|
После этого сканер представил полученную таблицу в специальном, описанном ниже формате и передал информацию на компьютер. Напишите программу, которая по полученной информации установит:
Пункт 1. Сколько клеток было вырезано из листа?
Пункт 2. Сколько фигур было вырезано?
Описание формата представления таблицы
Последовательность подряд идущих по горизонтали или вертикали единиц будем называть полосой. Полосу можно задаеть 4 числами:
Всю таблицу разобьем на полосы, состоящие из единиц так, чтобы каждая единица принадлежала хотя бы одной полосе. При этом полосы могут пересекаться, а также накладываться. Таким образом, таблица представляется в виде описания всех полос, которое удовлетворяет трем дополнительным требованиям:
Заметим, что таблица может быть представлена в виде полос разными способами, но каждое представление позволяет однозначно восстановить таблицу.
Во входном файле записано сначала число \(P\) (1 или 2) — номер пункта задачи, ответ на который требуется получить. Далее записаны размеры исходного листа — числа \(M\) и \(N\) \((1 \le M \le 4000, 1 \le N \le 4000)\). Затем записано число \(K\) \((0 \le K \le 256000)\) — количество полос в описании полученной таблицы. Затем идет K четверок чисел, описывающих полосы (полосы перечисляются в порядке начальных клеток полос: по строкам сверху вниз, в строке — слева направо).
В выходной файл выведите искомое количество (если \(P=1\), то — количество клеток, вырезанных из листа, если \(P=2\), то — количество фигур, вырезанных из листа).
1 40 400 2 1 1 100 40 0 1 101 1
15959
2 40 400 2 1 1 100 40 1 1 101 1
2
Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут)
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.
Во входном файле записаны сначала числа N (\(2 \le N \le 100\)) и E (\(2 \le E \le N\)). Затем записано число M (\(0 \le M \le 100\)), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (\(2 \le K \le N\)) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
В выходной файл выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
5 2 2 4 1 1 3 2 4 10 5 20 3 5 10 4 15 2 40
40
Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W×H клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
При этом часть пути может оказаться вне доски. Например:
Фишки с координатами (1,3) и (4,4) могут быть соединены. Фишки с координатами (2,3) и (5,3) тоже могут быть соединены. А вот фишки с координатами (2,3) и (3,4) соединить нельзя – любой соединяющий их путь пересекает другие фишки.
Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или «мнимых клеток», расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).
Первая строка входного файла содержит два натуральных числа: W – ширина доски, H – высота доски (1≤W,H≤75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ «X» (заглавная английская буква «экс») обозначает фишку, символ «.» (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами – X1, Y1, X2, Y2, причём 1≤X1,X2≤W, 1≤Y1,Y2≤H. Здесь (X1, Y1) и (X2, Y2) – координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.
Для каждого запроса необходимо вывести одно целое число на отдельной строке – длину кратчайшего пути, или 0, если такого пути не существует.
5 4 XXXXX X...X XXX.X .XXX. 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0
5 6 0
4 4 XXXX XXXX XXXX XXXX 1 1 2 1 2 2 3 2 1 1 3 1 3 4 4 3 2 1 2 4 1 1 2 2 0 0 0 0
1 1 4 6 11 0
Карту местности условно разбили на квадраты, и посчитали среднюю высоту над уровнем моря для каждого квадрата.
Когда идет дождь, вода равномерно выпадает на все квадраты. Если один из четырех соседних с данным квадратом квадратов имеет меньшую высоту над уровнем моря, то вода с текущего квадрата стекает туда (и, если есть возможность, то дальше), если же все соседние квадраты имеют большую высоту, то вода скапливается в этом квадрате.
Разрешается в некоторых квадратах построить водостоки. Когда на каком-то квадрате строят водосток, то вся вода, которая раньше скапливалась в этом квадрате, будет утекать в водосток.
Если есть группа квадратов, имеющих одинаковую высоту и образующих связную область, то если хотя бы рядом с одним из этих квадратов есть квадрат, имеющий меньшую высоту, то вся вода утекает туда, если же такого квадрата нет, то вода стоит во всех этих квадратах. При этом достаточно построить водосток в любом из этих квадратов, и вся вода с них будет утекать в этот водосток.
Требуется определить, какое минимальное количество водостоков нужно построить, чтобы после дождя вся вода утекала в водостоки.
Во входном файле записаны сначала числа N и M, задающие размеры карты — натуральные числа, не превышающие 100. Далее идет N строк, по M чисел в каждой, задающих высоту квадратов карты над уровнем моря. Высота задается натуральным числом, не превышающим 10000. Считается, что квадраты, расположенные за пределами карты, имеют высоту 10001 (то есть вода никогда не утекает за пределы карты).
В выходной файл выведите минимальное количество водостоков, которое необходимо построить.
4 4 1 2 4 1 2 4 4 4 1 4 3 2 1 2 3 2
4
В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.
Аттракцион заключается в том, что участника ставят в некоторой клетке спортзала и просят как можно быстрее добежать до некоторой другой клетки. При этом накладываются следующие условия:
Известно, что на то, чтобы перебежать из клетки в соседнюю, участник тратит ровно 1 секунду. Требуется вычислить минимальное время, за которое участник сможет достичь конечной клетки.
Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.
В выходной файл выведите минимальное время, за которое можно добраться в конечную клетку. Если попасть в конечную клетку с соблюдением всех условий нельзя, выведите –1.
1 3 4 0 0 2 0 0 1 1 0 0 0 3 0
6
0 5 5 0 1 0 0 0 0 1 0 1 0 0 0 3 1 0 1 0 1 1 0 2 0 0 0 0
12