Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]
dq1 = deque([])

while dq:
    r, c, cur_cost = dq.popleft()
    dq1.append((r, c, cur_cost))

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.append((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    if not dq:
        while dq1:
            r, c, cur_cost = dq1.popleft()

            for x in range(-2, 3):
                r_new = r + x
                if r_new < 0 or r_new >= H:
                    continue

                for y in range(-2, 3):
                    c_new = c + y

                    if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                        continue

                    dq.append((r_new, c_new, cur_cost + 1))
                    search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])


Fixed submission:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])


Fixed submission:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]

search = [[float('inf')] * W for _ in range(H)]
visit = [[False] * W for _ in range(H)]
dq = deque([])

dq.append((Ch, Cw))
search[Ch][Cw] = 0
visit[Ch][Cw] = True

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    cur_row, cur_col = dq.popleft()
    cur_step = search[cur_row][cur_col]

    dq_in = deque([])
    dq_in.append((cur_row, cur_col))

    warp_can = []
    while dq_in:
        r, c = dq_in.popleft()

        flag = False
        for dir_y, dir_x in direction:
            new_row = r + dir_x
            new_col = c + dir_y

            if new_row < 0 or new_row >= H or new_col < 0 or new_col >= W:
                continue

            if visit[new_row][new_col]:
                continue

            if grid[new_row][new_col] == '#':
                if not flag:
                    warp_can.append((r, c))
                    flag = True
            else:
                search[new_row][new_col] = cur_step
                dq_in.append((new_row, new_col))

        visit[r][c] = True

    next_island = []
    for w_row, w_col in warp_can:
        for r in range(-2, 3):
            x_row = w_row + r
            for c in range(-2, 3):
                if r == 0 and c == 0:
                    continue

                x_col = w_col + c

                if x_row < 0 or x_row >= H or x_col < 0 or x_col >= W:
                    continue

                if grid[x_row][x_col] == '#':
                    continue

                if visit[x_row][x_col]:
                    continue

                next_island.append((x_row, x_col))

    for x, y in next_island:
        dq.append((x, y))
        search[x][y] = min(cur_step + 1, search[x][y])


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])




Fixed submission:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]

search = [[float('inf')] * W for _ in range(H)]
visit = [[False] * W for _ in range(H)]
dq = deque([])

dq.append((Ch, Cw))
search[Ch][Cw] = 0
visit[Ch][Cw] = True

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    cur_row, cur_col = dq.popleft()
    cur_step = search[cur_row][cur_col]

    dq_in = deque([])
    dq_in.append((cur_row, cur_col))

    warp_can = []
    while dq_in:
        r, c = dq_in.popleft()

        flag = False
        for dir_y, dir_x in direction:
            new_row = r + dir_x
            new_col = c + dir_y

            if new_row < 0 or new_row >= H or new_col < 0 or new_col >= W:
                continue

            if visit[new_row][new_col]:
                continue

            if grid[new_row][new_col] == '#':
                if not flag:
                    warp_can.append((r, c))
                    flag = True
            else:
                search[new_row][new_col] = cur_step
                dq_in.append((new_row, new_col))

        visit[r][c] = True

    next_island = []
    for w_row, w_col in warp_can:
        for r in range(-2, 3):
            x_row = w_row + r
            for c in range(-2, 3):
                if r == 0 and c == 0:
                    continue

                x_col = w_col + c

                if x_row < 0 or x_row >= H or x_col < 0 or x_col >= W:
                    continue


                if grid[x_row][x_col] == '#':
                    continue



                if visit[x_row][x_col]:
                    continue

                next_island.append((x_row, x_col))

    for x, y in next_island:
        dq.append((x, y))
        search[x][y] = min(cur_step + 1, search[x][y])


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])




Fixed submission:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])