Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12510 - Collecting Coins (この記事を編集する[管理者用])

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12510

問題概要

r*cのグリッドが与えられる.(10*10以下)
スタート地点,障害物,岩,コインがある.
岩は5個以下,コインは10個以下.
最大で何個のコインを広いことができるかを求める問題.
上下左右に移動でき,岩は,各岩につき,1回だけ押して移動させることができる.
移動させた先は何もないマスで無くてはならないし,グリッドの外に押し出すこともできない.

解法

岩押す方向は4^5通り,岩を押す順番は5!なので全通り探索できる.
コインを全部拾えたら枝刈りすると超速くなった.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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