AOJ 0213 （Subdivide The Land : 土地分割）

【問題】

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0213?year=2009

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0213

【解説】

バックトラック法での全探索＋枝刈り。

各購入者の区画が長方形であるため、区画の横幅は面積の約数となる。それぞれの横幅に対し、看板の位置が含まれる配置（縦のインデックスをi,横のインデックスをjとすると、i-縦幅+1〜i,j-横幅+1〜jの範囲）をバックトラック法にて探索していく。

その際に長方形の左上または右下がエリア外または、エリア内に他の区画が含まれる場合は、枝刈りすることで処理時間を落とす。

答えが複数ある場合はNAとするため、答えが見つかっても、複数の答えが見つかるまでは処理を継続する点に注意。（以下のコードでは、答えが複数見つかった時点でtrueを返し、処理を打ち切る。）