「某社の採用試験は迷路の最短経路探索プログラム」記事へのコメント

プログラミング問題と言うよりは

[signed-coward (17953)]

アルゴリズム知識問題という気がしました。
経路探索系アルゴリズムを知っているかどうかで、
時間内に回答できるかどうかが決まると思います。

# 幅優先探索あたりを知ってれば解けるなぁ、とは思いましたが、
# 世の中にはもっと良いアルゴリズムがあるのかもしれない。

Re:プログラミング問題と言うよりは

[Anonymous Coward]

ダイクストラとかA*とかまでいかなくても
幅優先探索でいけないでしょうか？
Pythonで書いてみました。

board=[list(l.rstrip("\n")) for l in sys.stdin]

h, w=len(board), len(board[0])

cache=[[None for _ in xrange(w)] for _ in xrange(h)]
queue=[]

for y in xrange(h) :
        for x in xrange(w) :
                if board[y][x]=="S" :
                        bx, by=x, y
                if board[y][x]=="G" :
                        ex, ey=x, y

queue.append((bx, by))
cache[by][bx]=[]

px, py=queue.pop(0)

while px!=ex or py!=ey :
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)] :
                x, y=px+dx, py+dy

                if 0<=x<w and 0<=y<h and board[y][x]!="*" and cache[y][x]==None :
                        queue.append((x, y))
                        cache[y][x]=cache[py][px]+[(px, py)]

        px, py=queue.pop(0)

for x, y in cache[ey][ex][1:] :
        board[y][x]="$"

print "\n".join("".join(l) for l in board)