Pythonで迷路の最短路(幅優先検索)

大きさがN*Mの迷路が与えられます。迷路は通路と壁からできており、1ターンに隣接する上下左右4マスの通路へ移動することができます。スタートからゴールまで移動するのに必要な最小のターン数を求めなさい。

幅優先検索(BFS: Breadth-First Search)を使う

# coding=utf-8

def debug_print(maze):
    for xx in maze:
        for yy in xx:
            print yy,
        print "\n",

def clear_maze(sx, sy, gx, gy, maze):

    debug_print(maze)

    INF = 100000000

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_x_length)] for j in range(field_y_length)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
                    queue.insert(0, (nx, ny))
                    distance[nx][ny] = distance[x][y] + 1


        return distance[gx][gy]

    return bfs()


maze = [
    ['#', 'S', '#', '#', '#', '#', '#', '#', '.', '#'],
    ['.', '.', '.', '.', '.', '.', '#', '.', '.', '#'],
    ['.', '#', '.', '#', '#', '.', '#', '#', '.', '#'],
    ['.', '#', '.', '.', '.', '.', '.', '.', '.', '.'],
    ['#', '#', '.', '#', '#', '.', '#', '#', '#', '#'],
    ['.', '.', '.', '.', '#', '.', '.', '.', '.', '#'],
    ['.', '#', '#', '#', '#', '#', '#', '#', '.', '#'],
    ['.', '.', '.', '.', '#', '.', '.', '.', '.', '.'],
    ['.', '#', '#', '#', '#', '.', '#', '#', '#', '.'],
    ['.', '.', '.', '.', '#', '.', '.', '.', 'G', '#'],
    ]

sx, sy = 0, 1 # スタート地点の座標
gx, gy = 9, 8 # ゴール地点の座標
print clear_maze(sx, sy, gx, gy, maze)

実行結果

# S # # # # # # . # 
. . . . . . # . . # 
. # . # # . # # . # 
. # . . . . . . . . 
# # . # # . # # # # 
. . . . # . . . . # 
. # # # # # # # . # 
. . . . # . . . . . 
. # # # # . # # # . 
. . . . # . . . G # 
22