迷路探索の変形。「カギと扉」を追加。
カギ"a"をとると、扉"A"を開くことができる。
ゴールは固定、スタート位置となりうる点を探す。
条件として、扉を一度も開かずにゴールへ行ってはいけない。
カギがなくて扉を開けないのもダメ。
全部で90分かかった。
解法は20分で思いついたが実装に30分ぐらい掛かってしまい、
マップ全体が正方形だと思い込んで40分ぐらいデバッグしたのが痛い。
以下評価方法に従ってスタート地点候補を一つずつ評価する。
1. 候補地点から探索開始して、カギとゴールを取れる限り取得
2. その候補地点での初回での探索でゴールを見つけてしまったら失敗（条件に合わない）
3. 何も見つけられなかったら失敗（たどり着けない）
4. カギを見つけられたら、マップを更新して見つけられたカギと扉を消して、再度探索。
5. ゴールを見つけられたらスタート地点になりうる。
カギの種類はアルファベットの数だけなので最大26回ループ。
探索はN * M = 50 * 50 = 最大2500個
候補地点も同じく最大2500個
理論的には1億超えてしまうが実際の候補地点は壁があるので半分程度。
問題的にはどうにかなったっぽいが、チャレンジとかされたら多分ダメなんだろうな。