土地分割
2010.01.21 20:30 ACM/ICPC 2009
パソコン甲子園2009 問題09 土地分割
X×Y個のマスから成るグリッドで表された分譲地を、長方形の区画に分割する問題です。各区画の大きさ(マスの数)とその区画が含まなければならないマス(看板で示されています)が入力として与えられます。
全ての区画について順番に、要求された大きさの長方形で分譲地を埋めていきます。各区画の長方形の大きさと位置については、すでに決定した他の区画と重ならずかつ分譲地からはみ出さないような全てのパタンについて調べます。この処理は、再帰関数によって実装します。全ての区画について長方形が配置できかつ全てのマスが0以外で埋まっている場合は解としてカウントし、そうでない場合はバックトラックでさらに探索を行います。
X×Y個のマスから成るグリッドで表された分譲地を、長方形の区画に分割する問題です。各区画の大きさ(マスの数)とその区画が含まなければならないマス(看板で示されています)が入力として与えられます。
全ての区画について順番に、要求された大きさの長方形で分譲地を埋めていきます。各区画の長方形の大きさと位置については、すでに決定した他の区画と重ならずかつ分譲地からはみ出さないような全てのパタンについて調べます。この処理は、再帰関数によって実装します。全ての区画について長方形が配置できかつ全てのマスが0以外で埋まっている場合は解としてカウントし、そうでない場合はバックトラックでさらに探索を行います。
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |