Submission #5625749

---

Source Code Expand

from collections import deque

import sys
input = sys.stdin.readline
def main():
    size = map(int, input().split())
    sy, sx = map(int, input().split())
    gy, gx = map(int, input().split())
    maze = [input().rstrip() for _ in range(size[0])]

    start = (sy - 1, sx - 1)
    goal = (gy - 1, gx - 1)
    print(solve(maze, size, start, goal))

def solve(maze, size, start, goal):
    queue = deque([start])
    next_pos = []
    dist = [[None for _ in range(size[1])] for _ in range(size[0])]
    dist[start[0]][start[1]] = 0
    while goal not in next_pos:
        queue.extend(next_pos)
        go = queue.popleft()
        next_pos = [pos for pos in travel(maze, size, go) if dist[pos[0]][pos[1]] is None]
        cost = dist[go[0]][go[1]] + 1
        for p in next_pos:
            dist[p[0]][p[1]] = cost
    return dist[goal[0]][goal[1]]

def travel(maze, size, current_pos):
    x, y = current_pos
    next_pos = filter(
        lambda pos: pos[0] >= 0 and pos[1] >= 0 and pos[0] < size[0] and pos[1] < size[1],
        [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]
    )
    return filter(lambda pos: maze[pos[0]][pos[1]] == '.', next_pos)

if __name__ == '__main__':
    main()

Submission Info

Judge Result