시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 50 | 23 | 20 | 46.512% |
情報オリンピックの宣伝のために,長方形のベニヤ板にペンキを塗り看板を制作 したい.ベニヤ板には色を塗りたくないところにあらかじめ何枚かの長方形のマス キングテープが貼られている.そこでマスキングテープで区切られた領域ごとに別々 の色を使いペンキを塗ることにした.例えば,図 5-1 の場合は 5 色のペンキを使う.
図 5-1 看板の例
入力としてマスキングテープを貼る位置が与えられた時,使うペンキの色の数を 求めるプログラムを作成せよ.ただし,ベニヤ板全体がマスキングテープで覆われる ことはなく,全てのマスキングテープの辺はベニヤ板のいずれかの辺に平行である.
1 行目にはベニヤ板の幅 w (1 ≤ w ≤ 1000000 となる整数) と高さ h (1 ≤ h ≤ 1000000 となる整数) がこの順に空白区切りで書かれている.
2 行目にはマスキングテープの数 n (1 ≤ n ≤ 1000 となる整数) が書かれている. 続く 3 行目以降の 2 + i 行目 (1 ≤ i ≤ n) には,i 番目に貼るマスキングテープの左 下の座標 (x1, y1) と,右上の座標 (x2, y2) が x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ w, 0 ≤ y1 < y2 ≤ h となる整数) の順に空白区切りで書かれている.
ただし,ベニヤ板の左下の角の座標は (0, 0) で右上の角の座標は (w, h) である.
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
5
図 5-2 図 5-1 の看板の入力例