タイムアタックなので変数名は適当。
一応そのまま公開。

#coding:UTF-8
import sys
def rootsearch(root,hosu):
    allroot = []
    if root[-1] == goal:
        return root
    hosu += 1
    now = map(int,root[-1].split("-"))
    for x in [[now[0]+1,now[1]],[now[0],now[1]+1],[now[0]-1,now[1]],[now[0],now[1]-1]]:
        if m[x[0]][x[1]] == " " or (m[x[0]][x[1]].isdigit() and hosu < int(m[x[0]][x[1]])):
            m[x[0]][x[1]] = str(hosu)
            test = rootsearch(root+[str(x[0])+"-"+str(x[1])],hosu)
            if test != []: allroot = test
    return allroot

if __name__ == "__main__":
    meiro = open(sys.argv[1],"r").read()
    m = map(list,meiro.split("\n"))
    m2 = map(list,meiro.split("\n"))
    n = 0
    for a in m:
        if "S" in a:
            root = [str(n)+"-"+str(a.index("S"))]
        if "G" in a:
            goal = str(n)+"-"+str(a.index("G"))
            m[n][a.index("G")] = " "
        n += 1
    hosu = 0
    allroot = rootsearch(root,hosu)
    strings = ""
    for a in allroot[1:-1]:
        now = map(int,a.split("-"))
        m2[now[0]][now[1]] = "$"
    for a in m2:
        strings +=  "".join(a)+"\n"
    print strings
    open(sys.argv[2], "w").write(strings)

アルゴリズムの知識は皆無なので無難に総当たりで一番最短だったルートを採用。
それだけだとロスが多すぎるので通った所に歩数を付けて次からはその値以下の歩数でしか通れないようにする。こうすれば後戻りとか明らかに要らない処理を省ける。

で、大体上のアルゴリズムを思いつくのに30秒。作るのに20分程度。最終的には1時間20分程度。正直アルゴリズムよりコーディングに手間取った。特にうっかりリストのインデックスが0から始まるのを忘れるという有り得ない間違いでだいぶ時間をくってる。

その他、自分で見ても手癖が悪いと思う部分があるのでここら辺に無い実力が出てると思う。（例えばn += 1ってなんだよ！enumerate()使えよ！とか）

ソースの長さは短い方っぽいけどまあPythonだしどっちでもいいや
ちなみにこのソースだと問題元と同じルートを辿らない。9行目の順番を変えればおｋ

---

知識問題云々は正直カンケー無いんじゃないかなあ。自分みたいに知らなくてもアルゴリズムはすぐ思いつくだろうし。

むしろそのアルゴリズムをプログラムに落とし込むのに手間取ってるんじゃないかな。アルゴリズムを知っていても落とし込む能力が無きゃ書けないよな。

と考えて、ふと頭を過ぎったのが思考は言語に影響されるって話。
人材獲得作戦・３

キューやリストが必要なのは明らかなのに、言語にCを使う人が相当多い。

こういう人は必要が明らかな事も分からないんじゃないかな。他の言語を知らなければ。
もっと言えばプログラミング言語の考え方を分からない人は↑で言ったアルゴリズムも思い浮かばないのかも。いわばスタートラインにも立てなかった人たちなんだろうかね。
分からないけど。

自分はまあ今回は立てたっぽいけど、流石にPython一つだけだと心配だなあ。いつCの人の立場に立つか分からないし。
グダグダ過ぎるので別にPythonを使った方々の解答を貼ってお茶を濁して終了。

• 人材獲得作戦の試験問題を解いてみた - 良いもの。悪いもの。はてな部屋
• 人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題 - 黄コーダ－になりたい
• 迷路問題（人材獲得作戦・４）を解いてみる - 銀月の符号
• 「人材獲得作戦・４　試験問題ほか」を解いてみた(1) | 山本隆の開発日誌
• 「人材獲得作戦・４　試験問題ほか」を解いてみた(2) | 山本隆の開発日誌