Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2349-7321842e
この記事にトラックバックする(FC2ブログユーザー)

UVa 12500 - Balance the Blocks (この記事を編集する[管理者用])

Source

Another Bangladeshi Contest (2012-10-07)
UVa 12500

問題概要

4*4のグリッドに9個以下の動かせないブロックと,8個以下の動かせるブロックが置いてある.
両方のブロックがあるセルには,動かせるブロックのほうが必ず上にある.
ブロックがあるすべてのセルに対して,高さを同じにする最小ターン数を求める問題.
1ターンでは1回移動でき,移動するときは,上下左右に移動.
ただし,ブロックを押さない場合は,移動先と移動前のセルの高さの差は1以下でなくてはいけない.
ブロックを押す場合は,移動先の一番上のブロックのみ押せて,押し出した先のほうが高ければ押せない.
また,グリッドの外に押し出すこともできない.
移動先の方が高さが低ければ押せないが,高さが2高い場合は,ジャンブしながら押して,移動することができる.

解法

枝刈り全探索BFSで通った.
枝刈りは,最終的に揃えれる高さを列挙して,それに矛盾するような配置が存在すれば枝を刈った.
例えば,高さ1に揃えなくてはいけないのに,角に高さ2のセルがあるなど.
使った性質は,角は高さが減らない,端の4辺の合計ブロック数も減らない,ブロックのあるセルの数は減らないなど.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2349-7321842e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。