Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4645 - Infected Land (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4645
PKU 3811 (2011-01-21 04:29追加)
Aizu 1304

問題概要

5*5のマップがあって,幾つかがウイルスに汚染されている.
自分は毎ターンの最初に隣接8マスのどこかに移動しなければならない.ウイルスに汚染されてるマスには移動できない.
毎ターンの終わりに,各マスは,隣接8マスでウイルスに汚染されているマスの数A,自分のいるマスの数B (B=0 or 1)の情報をもとに
 自分がウイルスに汚染されていて,A+Bが2か3以外なら,ウイルスから解放される
 自分がウイルスに汚染されていなくて,A+Bが3なら,ウイルスに汚染される
ということを繰り返す.
自分が上手く動けば,最小で何ターンで,全てのウイルスが無くなるか,を求める問題.
不可能なら,それを指摘する.

解法

状態数が25*2^25で,幅優先探索.ビット演算使えば速い.
が妥当だと思うんだけど,答えがない場合を忘れていて,答えに適当な上限(仮定)を設けてiterative deepeningで解いた.
(どうやらジャッジデータに含まれてる最大の答えは10らしい…)

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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