■

某人材獲得がどーのこーの問題。

b.py

# -*- coding: utf-8 -*-
import sys

m = [list(line[:-1]) for line in sys.stdin]
q = []
for i in range(len(m)):
    for j in range(len(m[i])):
        if m[i][j] == 'S':
            q.append((i, j, [(i, j)]))
            break

i = j = path = ''
visited = []
while q:
    i, j, path = q.pop(0)
    if m[i][j] == 'G':
        break
    else:
        for y, x in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
            if not (y, x) in visited and m[y][x] in (' ', 'G'):
                visited.append((y, x))
                q.append((y, x, path+[(y, x)]))

for i, j in path:
    if not m[i][j] in ('S', 'G'):
        m[i][j] = '$'

print '\n'.join([''.join(L) for L in m])

map.dat

**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************

実行、結果

$ python b.py < map.dat
**************************
*S* *$$$$                *
*$* *$ *$ *************  *
*$*$$$* $  ************  *
*$$$ *  $$$$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$  *$$$$$$$$$$$$$$G  *
*  *$$$$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************

「こんなもん幅優先探索するだけだし、10分もあれば書けるだろ……」とか思ってやってみたものの、なんだかんだで30分近くかかったので死にたいですね。