人材獲得作戦・４

TLで見かけた問題を解いてみた。
http://okajima.air-nifty.com/b/2010/01/post-abc6.html
ん・・・これだとLv.3になるのかな？いや大丈夫だよね。

file_name = "maze.txt"
f = open(file_name, 'r')
maze = []
start = None
goal = None
x = 0
y = 0
for line in f.readlines():
    d = []
    x = 0
    for c in line:
        d.append(c)
        if (c == 'S'):
            start = (x, y)
        elif (c == 'G'):
            goal = (x, y)
        x += 1
    maze.append(d)
    y += 1

x_size = len(maze[0])
y_size = len(maze)
visited = []
for i in range(y_size):
    d = []
    for j in range(x_size):
        d.append({'v':False, 's':-1})
    visited.append(d)
        
queue = []
queue.append((start[0], start[1], 0))

while queue:
    x, y, s = queue.pop(0)
    visited[y][x]['v'] = True
    visited[y][x]['s'] = s
    s += 1
    
    for x2, y2 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
        if not (x2 < 0 or x2 >= x_size or y2 < 0 or y2 >= y_size):
            if (maze[y2][x2] == '*'):
                continue

            if not visited[y2][x2]['v'] or visited[y2][x2]['s'] > s:
                queue.append((x2, y2, s))

x = goal[0]
y = goal[1]
s = visited[y][x]['s']

while 1:
    if (x, y) == start:
        break
    
    for x2, y2 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
        if not (x2 < 0 or x2 >= x_size or y2 < 0 or y2 >= y_size):
            if (maze[y2][x2] == '*'):
                continue

            if visited[y2][x2]['s'] == s - 1:
                maze[y2][x2] = '$'
                s -= 1
                x = x2
                y = y2
                break

for i in range(y_size):
    print ''.join(maze[i])