WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Forest"問題http://codeforces.com/contest/330/problem/D訳あなたはミケモンマスターになるための旅をしているミケモンブリーダーである。あなたは悪名高いブリディアンの森を抜けるのに苦労している。・ブリディアンの森ブリディアンの森は2次元のr行c列のマスで構成されたものである。それぞれのマスには木が生えているか、空である。空のマスには0人以上のミケモンブリーダーがいる。ミケモンブリーダーは(あなたを含め)木の生えているマスに入る事はできない。マスの1つは森の出口のマスとなっている。初期のマスの情報は、あなたの初期位置と、出口のマスと、そして他のブリーダーの初期位置がある。・動きブリーダーは(あなたも含め)森の中で行動をとる。一回の行動で、下記の中の1つの動きをする。・待機する・現在いるマスから隣のマスに移動する。(木のマスには移動できない)・出口のマスにいるのなら、森から抜け出す。この行動はあなたしか行わない。あなたが一回行動をとると、他のブリーダーが同時に一回行動をとる(どのように行動をとるかはブリーダーそれぞれで異なっていてもよい)・ミケモンバトルもし、あなたとt人のミケモンブリーダーが同じマスに入ったとき、ちょうどt回ミケモンバトルが起こる。バトルの後、彼らは彼らのミケモンをミケモンセンターで癒すため、森から立ち去る。あなたが森から脱出した後は、即座に他のブリーダーが出口マスに移動したとしても、ミケモンバトルはそれ以上起こらない。それから、ミケモンバトルは、あなたと他のブリーダーとの間でしか起こらない(たとえ他のブリーダーが同じマスに同時に入ったとしてもバトルは起こらない)。・あなたの目的あなたは森から脱出したい。するために、あなたは複数の行動をとり、最後の種類の動きを行う(つまり出口マス上で抜け出す動作)。あなたは既に森を脱出するまでに、どう行動をとるかについて、あなたのブログに乗せていた。あなたはブログに乗せたものに忠実に動くことになる。・他のブリーダーの目的あなたがブログに行動について書いたことにより、他のブリーダーにあなたがどう行動をとるか、確実に分かっている。彼らは可能であれば、あなたとミケモンバトルが起きるよう、行動をとるだろう。なければ、彼らは待機している。最善の行動をとり、森から脱出するまでのミケモンバトルの回数を最小化し、それを出力せよ。出口までの最短距離が、主人公よりも近いか同じブリーダーは、出口で待ち伏せする事により、ミケモンバトルを起こす事ができる。他のブリーダーにとって最善の行動はこのように出口で待ち伏せする事である。よって、主人公の最善の行動は、最短距離を歩く事である。ゴールを起点としたBFSなどで、最短距離が主人公と同じかそれ以下のブリーダーの数を数えればよい。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。