Buggy python submission (verdict: Time Limit Exceeded):
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = [IS() for _ in range(h)]
    check = [[-1]*w for i in range(h)]
    dq = deque([(ch-1, cw-1)])
    check[ch-1][cw-1] = 0
    count = 0

    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1

    while True:
        tmp = []
        while dq:
            y, x = dq.popleft()
            tmp.append((y, x))
            for dy, dx in ((0,1), (0,-1), (1,0), (-1,0)):
                ny = y+dy
                nx = x+dx
                if not inMaze(nx, ny):
                    continue
                if isWall(nx, ny):
                    continue
                if isChecked(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in tmp:
            for i in range(-2,3):
                for j in range(-2,3):
                    ny = y+i
                    nx = x+j
                    if not inMaze(nx, ny):
                        continue
                    if isWall(nx, ny):
                        continue
                    if isChecked(nx, ny):
                        continue
                    check[ny][nx] = count
                    dq.append((ny, nx))
        if not dq:
            break

    print(check[dh-1][dw-1])

if __name__ == '__main__':
    main()

Fixed submission:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = [IS() for _ in range(h)]
    check = [[-1]*w for i in range(h)]
    dq = deque([(ch-1, cw-1)])
    check[ch-1][cw-1] = 0
    count = 0

    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1

    while True:
        tmp = []
        while dq:
            y, x = dq.popleft()
            tmp.append((y, x))
            for dy, dx in ((0,1), (0,-1), (1,0), (-1,0)):
                ny = y+dy
                nx = x+dx
                if not inMaze(nx, ny):
                    continue
                if isWall(nx, ny):
                    continue
                if isChecked(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in tmp:
            for i in range(-2,3):
                for j in range(-2,3):
                    ny = y+i
                    nx = x+j
                    if not inMaze(nx, ny):
                        continue
                    if isWall(nx, ny):
                        continue
                    if isChecked(nx, ny):
                        continue
                    check[ny][nx] = count
                    dq.append((ny, nx))
        if not dq:
            break

    print(check[dh-1][dw-1])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = []
    for i in range(2):
        maze.append(['#']*(w+4))
    for i in range(h):
        maze.append(['#']*2 + list(IS()) + ['#']*2)
    for i in range(2):
        maze.append(['#']*(w+4))

    seen_cost0 = set()
    seen_cost1 = set()
    def bfs(maze, y, x):
        dq = deque()
        dq.append((y, x, 0))
        while dq:
            now_y, now_x, now_count = dq.popleft()
            if now_y == dh+1 and now_x == dw+1:
                return now_count
            # cost 0 でたどり着けるマス
            maze[now_y][now_x] == '#'
            for dx, dy in [(1,0), (-1,0), (0, 1), (0, -1)]:
                nx = now_x + dx
                ny = now_y + dy
                if maze[ny][nx] == '#':
                    continue
                maze[ny][nx] = '#'
                seen_cost0.add((ny, nx))
                dq.appendleft((ny, nx, now_count))
            # cost 1 でたどり着けるマス
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    if dx == dy == 0: continue
                    nx = now_x + dx
                    ny = now_y + dy
                    if maze[ny][nx] == '#':
                        continue
                    if (ny, nx) in seen_cost0:
                        continue
                    dq.append((ny, nx, now_count+1))
        return None

    res = bfs(maze, ch+1, cw+1)
    if res is not None:
        print(res)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = [IS() for _ in range(h)]
    check = [[-1]*w for i in range(h)]
    dq = deque([(ch-1, cw-1)])
    check[ch-1][cw-1] = 0
    count = 0

    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1

    while True:
        tmp = []
        while dq:
            y, x = dq.popleft()
            tmp.append((y, x))
            for dy, dx in ((0,1), (0,-1), (1,0), (-1,0)):
                ny = y+dy
                nx = x+dx
                if not inMaze(nx, ny):
                    continue
                if isWall(nx, ny):
                    continue
                if isChecked(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in tmp:
            for i in range(-2,3):
                for j in range(-2,3):
                    ny = y+i
                    nx = x+j
                    if not inMaze(nx, ny):
                        continue
                    if isWall(nx, ny):
                        continue
                    if isChecked(nx, ny):
                        continue
                    check[ny][nx] = count
                    dq.append((ny, nx))
        if not dq:
            break

    print(check[dh-1][dw-1])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = []
    for i in range(2):
        maze.append(['#']*(w+4))
    for i in range(h):
        maze.append(['#']*2 + list(IS()) + ['#']*2)
    for i in range(2):
        maze.append(['#']*(w+4))

    seen = set()
    def bfs(maze, y, x):
        dq = deque()
        dq.append((y, x, 0))
        while dq:
            now_y, now_x, now_count = dq.popleft()
            if now_y == dh+1 and now_x == dw+1:
                return now_count
            # cost 0 でたどり着けるマス
            maze[now_y][now_x] == '#'
            for dx, dy in [(1,0), (-1,0), (0, 1), (0, -1)]:
                nx = now_x + dx
                ny = now_y + dy
                if maze[ny][nx] == '#':
                    continue
                maze[ny][nx] = '#'
                dq.appendleft((ny, nx, now_count))
            # cost 1 でたどり着けるマス
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    if dx == dy == 0: continue
                    nx = now_x + dx
                    ny = now_y + dy
                    if maze[ny][nx] == '#':
                        continue
                    dq.append((ny, nx, now_count+1))
        return None

    res = bfs(maze, ch+1, cw+1)
    if res is not None:
        print(res)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = [IS() for _ in range(h)]
    check = [[-1]*w for i in range(h)]
    dq = deque([(ch-1, cw-1)])
    check[ch-1][cw-1] = 0
    count = 0

    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1

    while True:
        tmp = []
        while dq:
            y, x = dq.popleft()
            tmp.append((y, x))
            for dy, dx in ((0,1), (0,-1), (1,0), (-1,0)):
                ny = y+dy
                nx = x+dx
                if not inMaze(nx, ny):
                    continue
                if isWall(nx, ny):
                    continue
                if isChecked(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in tmp:
            for i in range(-2,3):
                for j in range(-2,3):
                    ny = y+i
                    nx = x+j
                    if not inMaze(nx, ny):
                        continue
                    if isWall(nx, ny):
                        continue
                    if isChecked(nx, ny):
                        continue
                    check[ny][nx] = count
                    dq.append((ny, nx))
        if not dq:
            break

    print(check[dh-1][dw-1])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = []
    for i in range(2):
        maze.append(['#']*(w+4))
    for i in range(h):
        maze.append(['#']*2 + list(IS()) + ['#']*2)
    for i in range(2):
        maze.append(['#']*(w+4))

    seen = set()
    def bfs(maze, y, x):
        dq = deque()
        dq.append((y, x, 0))
        while dq:
            now_y, now_x, now_count = dq.popleft()
            if now_y == dh+1 and now_x == dw+1:
                return now_count
            # cost 0 でたどり着けるマス
            maze[now_y][now_x] == '#'
            for dx, dy in [(1,0), (-1,0), (0, 1), (0, -1)]:
                nx = now_x + dx
                ny = now_y + dy
                if maze[ny][nx] == '#':
                    continue
                maze[ny][nx] = '#'
                dq.appendleft((ny, nx, now_count))
            # cost 1 でたどり着けるマス
            for dx in range(-2, 3, 1):
                for dy in range(-2, 3, 1):
                    if dx == dy == 0: continue
                    nx = now_x + dx
                    ny = now_y + dy
                    if maze[ny][nx] == '#':
                        continue
                    dq.append((ny, nx, now_count+1))
        return None

    res = bfs(maze, ch+1, cw+1)
    if res is not None:
        print(res)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = [IS() for _ in range(h)]
    check = [[-1]*w for i in range(h)]
    dq = deque([(ch-1, cw-1)])
    check[ch-1][cw-1] = 0
    count = 0

    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1

    while True:
        tmp = []
        while dq:
            y, x = dq.popleft()
            tmp.append((y, x))
            for dy, dx in ((0,1), (0,-1), (1,0), (-1,0)):
                ny = y+dy
                nx = x+dx
                if not inMaze(nx, ny):
                    continue
                if isWall(nx, ny):
                    continue
                if isChecked(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in tmp:
            for i in range(-2,3):
                for j in range(-2,3):
                    ny = y+i
                    nx = x+j
                    if not inMaze(nx, ny):
                        continue
                    if isWall(nx, ny):
                        continue
                    if isChecked(nx, ny):
                        continue
                    check[ny][nx] = count
                    dq.append((ny, nx))
        if not dq:
            break

    print(check[dh-1][dw-1])

if __name__ == '__main__':
    main()