[Python] ABC007 C

問題

C – 幅優先探索

幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

回答

row, col = map(int, input().split())
start_y, start_x = map(int, input().split())
goal_y, goal_x = map(int, input().split())
maze = [input() for _ in range(row)]

PATH = '.'
WALL = '#'

UP = [1, 0]
DOWN = [-1, 0]
RIGHT = [0, 1]
LEFT = [0, -1]

GOAL = [goal_y-1, goal_x-1]

queue = []
distance = [[-1]*col for _ in range(row)]

distance[start_y - 1][start_x - 1] = 0
queue.append([start_y - 1, start_x - 1])


while queue:
    current_y, current_x = queue.pop(0)
    if [current_y, current_x] == GOAL:
        print(distance[current_y][current_x])
        break
        
    for y, x in [UP, DOWN, RIGHT, LEFT]:
        next_y, next_x = current_y + y, current_x + x

        if maze[next_y][next_x] == PATH and \
            distance[next_y][next_x] < 0:

            queue.append([next_y, next_x])
            distance[next_y][next_x] = distance[current_y][current_x] + 1

print('could not reach the goal')