← 返回题目列表

AtCoder · joi2008ho_e

E. 油漆颜色

中文机器翻译题面 查看原题

配点: 20 点

为了宣传信息板,我们想在长方形的胶合板上涂漆制作招牌。在胶合板上,事先贴好了若干长方形的遮蔽胶带,以避免涂到不想涂色的地方。因此,决定在每个被遮蔽胶带分隔开的区域使用不同的颜色进行涂漆。例如,在图5-1的情况下 5 使用的涂料颜色为

图5-1 招牌示例

输入给出的是遮蔽胶带的贴附位置,制作程序以求出所需的涂料颜色数量。但胶合板整体不会被遮蔽胶带覆盖,且所有遮蔽胶带的边都与胶合板的某条边平行。


入力

1 行包含胶合板的宽度 w (1 \leqq w \leqq 1\,000\,000 (整数)和高度 h (1 \leqq h \leqq 1\,000\,000 (整数),以空格分隔按此顺序书写。2 行包含遮蔽胶带的数量 n (1 \leqq n \leqq 1\,000 所示的整数)。紧接着 3 行开始 2 + i 行目 (1 \leqq i \leqq n)有i 要贴的第几格遮蔽胶带的左下坐标 (x_1, y_1) 和右上坐标 (x_2, y_2) 是 在 x_1, y_1, x_2, y_2 (0 \leqq x_1 < x_2 \leqq w,0 \leqq y_1 < y_2 \leqq h 所示的整数)按空格分隔书写。

但是,胶合板的左下角坐标是 (0, 0) 右上角坐标是 (w, h) 。

评分数据中,分配的分数 30 % 是 w \leqq 100,h \leqq 100,n \leqq 100 很满意。

图 5-2 图 5-1 中符号的输入示例

出力

输出是 由 1 行组成,其 1 行仅包含要使用的油漆颜色的数量。


入力例 1

15 6
10
1 4 5 6
2 1 4 5
1 0 5 1
6 1 7 5
7 5 9 6
7 0 9 2
9 1 10 5
11 0 14 1
12 1 13 5
11 5 14 6

出力例 1

5

该示例如图 5-1 所示。