Time Limit: 1.5 sec / Memory Limit: 64 MB
配点: 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 の場合である.