人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題

30分くらい。
知らなければなかなか解けない問題だし仕事でこういうプログラム書くことは無いんだろうな、とは思う。

maze = open("input.txt","r").read().splitlines()

w = len(maze[0])
h = len(maze)
inf = w*h

for y in range(h):
    for x in range(w):
        if maze[y][x] == "S":
            sx = x; sy = y
        if maze[y][x] == "G":
            gx = x; gy = y

dist = [[(inf,)]*w for y in range(h)]

dist[sy][sx] = (0,)

for i in range(0,inf):
    if dist[gy][gx][0] < inf:
        break
    for y in range(h):
     for x in range(w):
        if dist[y][x][0] == i:
            for d in range(4):
                tx = x+[1,0,-1,0][d]
                ty = y+[0,1,0,-1][d]
                if ( 0 <= tx and tx < w and
                     0 <= ty and ty < h and
                     maze[ty][tx] != "*" and
                     dist[ty][tx][0] == inf ):
                    dist[ty][tx] = (i+1,(x,y))

(x,y) = dist[gy][gx][1]
while (x,y) != (sx,sy):
    maze[y] = maze[y][:x]+"$"+maze[y][x+1:]
    (x,y) = dist[y][x][1]

open("output.txt","w").write("\n".join(maze))

ブックマークコメントに触発されて短くしてみたけど、258B。

S=9801,                             //  99*99
d[99999],                           //  S - 到達時刻
*f,                                 //  移動元
g;                                  //  ゴールの位置
char*m,                             //  迷路
*p;
main(i,j,k,t)
{
    for(p=m=(f=d+S)+S;gets(p);p+=99);   //  入力

    for(i=S;i--;)
    for(j=S;j--;)
    for(k=4;k--;)
        g=m[j]-71?g:j,              //  ゴール位置を記録
        t=j+(1-(k&2))*(k%2*98+1),   //  移動先　t = j + {-1,-99,1,99}[k]

        !d[t]&                      //  tが未到達で
        (m[t]!=42&d[j]>i            //  tが*ではなく移動元の到達時刻がi+1
         |m[t]==83)?                //  もしくはtがSならば
            d[t]=i,f[t]=j:0;        //  tには時刻iで到達できる

    for(;m[g=f[g]]-83;m[g]=36);     //  最短経路に$を書く

    for(p=m;*p;p+=99)puts(p);       //  出力
}

もう少し短くなった。247B。

S=4096,                                 //  64*64
d[9999],                                //  (S-到達時刻)*S + 移動元
g;                                      //  ゴール位置
char*m,*p;                              //  盤面

main(i,j,k,t)
{
    for(p=m=d+S;gets(p);p+=64);         //  入力

    for(i=S;i--;)
    for(j=S;j--;)
    for(k=4;k--;)
    {
        g=m[j]-71?g:j,                  //  ゴール位置を記録
                                        //  移動先　t = j+{-1,-63,1,63}[k]
        !d[t=j+(1-(k&2))*(k%2*63+1)]&&  //  tに未到達で
        m[t]!=42&d[j]>i|                //  tが*ではなくjに到達している
        m[t]>82?                        //  もしくはjがSであるならば
            d[t]=i*S+j:0;               //  tには時刻iで到達可能
    }
    
    for(;m[g=d[g]%S]-83;m[g]=36);       //  最短経路に$を書く
    
    for(p=m;*p;p+=64)puts(p);           //  出力
}