アカウント名:
パスワード:
迷路の探索といえば、とにかく壁に当たるまで右か左に進んで、ダメだったら分岐を一つ一つ引き返して別の道を行くというLISPで書いたら楽しそうなアルゴリズムが思い付くけど、これだと問題によってはとてつもなく時間がかかって終わらないので、見当はずれの間違いってことじゃないものの、正解ではないらしい。
マップが小さいなら、水平探索を優先して全マス目を「そのマス目への最短到着経路」で埋め尽くして、Gに到着したらそれが最短、という手がある、Sに隣接するマス目を1、1に隣接するマス目を2…って埋めていく。もちろん、壁は数字でうめちゃダメね。この時に、Gの数字が最短ステップ。もちろん、Gが埋まったらそれ以上升目を埋める必要はない。
あとはSからGまでのパスを見つけるのだけれど、その際には「Gから逆に、マス目の数字が1づつ減るように」手繰っていく。複数候補がある場合は、適当に選ぶので構わない。Step0に到着したら、そこがSでなくちゃおかしい。
.
ただし、この方法が使えるには、地図が全部メモリ上に展開できて、なおかつ各マスに対して十分なメモリが割り当てられなくちゃいけない(たとえばステップ数カウントに4byte。仮の経路マークに1bit…は無理なので、alignment を考えてやはり4byte)。なので、一般解じゃない。
正規表現で言う DFA エンジンと同じなので、「一般解」にする場合は NFA エンジン(再帰探索エンジン)とのハイブリッドにしなくちゃいけない。そんなのが25分はもちろん、3時間で組めるわけがない。
なので、個人的な結論は「これは出題者側のレベルが低すぎて、問題として熟慮されていない」だと思うな。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
目玉の数さえ十分あれば、どんなバグも深刻ではない -- Eric Raymond
最短経路チェックが思いつかないわ (スコア:1)
マップが小さいなら、水平探索を優先して全マス目を「そのマス目への最短到着経路」で埋め尽くして、Gに到着したらそれが最短、という手がある、Sに隣接するマス目を1、1に隣接するマス目を2…って埋めていく。もちろん、壁は数字でうめちゃダメね。この時に、Gの数字が最短ステップ。もちろん、Gが埋まったらそれ以上升目を埋める必要はない。
あとはSからGまでのパスを見つけるのだけれど、その際には「Gから逆に、マス目の数字が1づつ減るように」手繰っていく。複数候補がある場合は、適当に選ぶので構わない。Step0に到着したら、そこがSでなくちゃおかしい。
.
ただし、この方法が使えるには、地図が全部メモリ上に展開できて、なおかつ各マスに対して十分なメモリが割り当てられなくちゃいけない(たとえばステップ数カウントに4byte。仮の経路マークに1bit…は無理なので、alignment を考えてやはり4byte)。なので、一般解じゃない。
正規表現で言う DFA エンジンと同じなので、「一般解」にする場合は NFA エンジン(再帰探索エンジン)とのハイブリッドにしなくちゃいけない。そんなのが25分はもちろん、3時間で組めるわけがない。
なので、個人的な結論は
「これは出題者側のレベルが低すぎて、問題として熟慮されていない」
だと思うな。
fjの教祖様