<ПРЕД Задача:
СЛЕД>
Задачу решили 139 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Вырезанные фигуры

Time limit = 8 секунд(ы)

Эпидемия гриппа не обошла стороной семиклассника Алешу. Скучая дома, Алеша решил вырезать фигурки из листа клетчатой бумаги, содержащей M строк и N столбцов. Сначала Алеша нарисовал на листе границы фигур. Количество фигур было не меньше 2. Чтобы фигуры получались ровными, границы фигур Алеша рисовал строго по линиям имеющейся клеточной разметки листа (при этом некоторые границы фигур могли пройти по границам листа). Форма фигур могла быть любой, но при этом все фигуры были связными (фигура называется связной, если из любой ее клетки можно добраться до любой другой, ходя только по клеткам фигуры и перемещаясь каждый раз в одну из 4-х соседних по стороне клеток). Никакие две фигуры не имели общих точек, в том числе не касались углами клеток.

Затем Алеша вырезал нарисованные фигуры, делая разрезы только по их границам. При этом оставшаяся часть листа осталась связной (то есть не распалась на несколько частей).

Лист с вырезами Алеша отсканировал. Сканер в своей памяти по результатам сканирования построил таблицу, состоящую из нулей и единиц, из M строк и N столбцов (строки нумеруются сверху вниз от 1 до M, стролбцы — слева направо от 1 до N). Каждый элемент таблицы соответствовал клеточке исходного листа. Единица обозначала, что соответствующая клетка листа осталась на месте, ноль — соответствующая клетка была вырезана.

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

Пункт 1. Сколько клеток было вырезано из листа?

Пункт 2. Сколько фигур было вырезано?

Описание формата представления таблицы

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

направление (0 — горизонтальная, 1 — вертикальная)

(i, j) — координаты начальной клетки полосы (начальной является самая левая клетка для горизонтальной полосы, и самая верхняя — для вертикальной), i — номер строки клетки, j — номер столбца

d — длина полосы (количество подряд стоящих единиц).

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

В каждой клетке начинается не более одной полосы.

Полосы перечислены в порядке следования их начальных клеток (клетки перечисляются по строкам сверху вниз, в строке — слева направо).

Общее число полос не превышает 256000.

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

Вход

Во входном файле записано сначала число P (1 или 2) — номер пункта задачи, ответ на который требуется получить. Далее записаны размеры исходного листа — числа M и N (1 ≤ M ≤ 4000, 1 ≤ N ≤ 4000). Затем записано число K (0 ≤ K ≤ 256000) — количество полос в описании полученной таблицы. Затем идет K четверок чисел, описывающих полосы (полосы перечисляются в порядке начальных клеток полос: по строкам сверху вниз, в строке — слева направо).

Выход

В выходной файл выведите искомое количество (если P=1, то — количество клеток, вырезанных из листа, если P=2, то — количество фигур, вырезанных из листа).

Вход#1
1
40 400
2
1 1 100 40
0 1 101 1
Выход#1
15959

Вход#2
2
40 400
2
1 1 100 40
1 1 101 1
Выход#2
2
 
Вход#3
1
6 12
17
0 1 1 10
1 1 4 4
0 1 5 2
0 1 7 6
1 2 1 5
1 2 5 4
0 2 6 1
1 2 12 5
0 3 4 4
0 3 10 3
0 4 2 2
1 4 11 3
1 5 2 1
0 5 6 2
1 5 9 2
0 6 1 2
0 6 5 7
Выход#3
22

Вход#4
2
6 12
12
0 1 1 12
1 1 12 6
1 2 1 5
0 2 4 3
0 3 4 4
0 3 10 3
1 3 11 4
0 4 1 5
1 5 2 2
0 5 5 3
1 5 9 2
0 6 5 8
Выход#4
3

Автор:
Олимпиада школьников московской области, 2004
15 Марта 2004

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 75.101.220.230