3338 Rectangle Cutting

原文

時間制限:2000ミリ秒
メモリ制限:65536KB

問題

Rectangle Cutting
長方形のケーキをカットする問題。
ある家族がケーキを分けるため長方形のケーキにケーキの縦横と平行にナイフのカットを入れてケーキを切り分けていく。
カットが行われた後ケーキが何個に分かれたかを出力してほしい。

ケーキは端っこを四角く切り取られることもあれば、ケーキの真ん中が四角く切り取られることもある。

カットはナイフを使い四角く行われ、カットする座標が与えられる。
一度のカットで４回の切断が行われる。
ケーキをカットするときケーキ上の座標として(x1,y1)(x2,y2)の頂点座標が与えられる。
例えば(1,1),(3,2)という座標が与えられた場合この範囲を四角く区切るため。

線分(1,1)～(3,1)
線分(3,1)～(3,2)
線分(3,2)～(1,2)
線分(1,2)～(1,1)
の４か所にナイフが入れられケーキの中の矩形範囲(1,1),(2,3)の部分が四角く切り取られる。
この４回ナイフを入れる操作を一回のカットと定義する。
ケーキには慎重にナイフが入れられ、ケーキは動かさずに複数回のカットがおこなわれる。
全てのカットが終わった後ケーキが何個に切られたかを出力せよ。

データは複数のデータセットが与えられる。

一つのデータセットは。

一行目にケーキの縦横サイズｈ<21、ｗ<21が整数で与えられる。
次の行にカットされる回数ｎ<=50が与えられる。
その次の行からｎ行にわたりカットする座標(x1,y1)(x2,y2)が整数で与えられる。
四角くカットされる範囲はx1<=x<=x2,y1<=y<=y2で定義される範囲である。
x1>x2やy1>y2のときはx2<=x<=x1,y2<=y<=y1などと定義する。

ｈ、ｗがともに0のとき入力の終了となる。

入力の例

3 5
3
1 1 3 2
4 0 2 3
4 0 5 1
6 6
2
2 0 5 3
3 1 4 2
0 0

出力の例

6
3

出典

Tehran 2006 Preliminary