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

def main():

    input = sys.stdin.readline

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

    S=[list(map(str,list(input()[:-1]))) for i in range(H)]
    F=[ [-1] * W for i in range(H)]
    dist=[ [10000000] * W for i in range(H)]

    dh = (1, 0, -1, 0)
    dw = (0, 1, 0, -1)
    warph = (2, 2, 2, 2 ,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2)
    warpw = (-2, -1, 0, 1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)

    d = deque()

    d.append((Ch-1,Cw-1))

    F[Ch-1][Cw-1] = 0
    dist[Ch-1][Cw-1] = 0

    while len(d) > 0:
        Ph,Pw = d.popleft()

        # if (Ph == Dh-1) & (Pw == Dw-1):
        #     goal = True
        #     break

        for i in range(4):
            nh = Ph + dh[i]
            nw = Pw + dw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.appendleft((nh,nw))
                F[nh][nw] = 0
            if dist[nh][nw] > dist[Ph][Pw]:
                dist[nh][nw] = dist[Ph][Pw]
                d.appendleft((nh,nw))

        for i in range(20):
            nh = Ph + warph[i]
            nw = Pw + warpw[i]
            if (nh < 0) | (nh >= H) | (nw < 0) | (nw >= W):
                continue
            if S[nh][nw] == "#":
                continue
            if F[nh][nw] == -1:
                d.append((nh,nw))
                F[nh][nw] = 0
            if dist[nh][nw] > dist[Ph][Pw] + 1:
                dist[nh][nw] = dist[Ph][Pw] + 1
                d.appendleft((nh,nw))

    if dist[Dh-1][Dw-1] >= 10000000:
        print("-1")
    else:
        print(dist[Dh-1][Dw-1])
         

if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.appendleft((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.appendleft((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

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

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx in range(-2,3):
                for dy in range(-2,3):
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.' and (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x]
                    elif S[sy][sx] == '.' and (dx,dy) not in ((-1,0),(1,0),(0,-1),(0,1)):
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x] + 1
                    elif (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        if S[sy][sx] > S[y][x]:
                            S[sy][sx] = S[y][x]
                            que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.appendleft((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.appendleft((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

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

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.append((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.append((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.appendleft((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.appendleft((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

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

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx in range(-2,3):
                for dy in range(-2,3):
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        cnt = 0
                    else:
                        cnt = 1
                    if S[sy][sx] == '.':
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x] + cnt
                    elif S[sy][sx] > S[y][x] + cnt:
                        S[sy][sx] = S[y][x] + cnt
                        que.append((sx,sy))
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

Fixed submission:
from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.appendleft((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.appendleft((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

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

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx in range(-2,3):
                for dy in range(-2,3):
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.' and (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x]
                    elif S[sy][sx] == '.' and (dx,dy) not in ((-1,0),(1,0),(0,-1),(0,1)):
                        que.append((sx,sy))
                        S[sy][sx] = S[y][x] + 1
                    elif (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1)):
                        if S[sy][sx] > S[y][x]:
                            S[sy][sx] = S[y][x]
                            que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()

Fixed submission:
from collections import deque
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Dh,Dw = map(int,input().split())
    S = [list(input()) for _ in range(H)]
    S[Ch-1][Cw-1] = 0

    def bfs(x,y):
        que = deque()
        que.append((x,y))

        while que:
            x,y = que.popleft()
            for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
                sx = x + dx
                sy = y + dy
                if sx < 0 or sx >= W or sy < 0 or sy >= H:
                    continue
                if S[sy][sx] == '#':
                    continue
                if S[sy][sx] == '.':
                    S[sy][sx] = S[y][x]
                    que.appendleft((sx,sy))        
                else:
                    if S[sy][sx] > S[y][x]:
                        S[sy][sx] = S[y][x]
                        que.appendleft((sx,sy)) 
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if (dx,dy) in ((-1,0),(1,0),(0,-1),(0,1),(0,0)):
                        continue
                    sx = x + dx
                    sy = y + dy
                    if sx < 0 or sx >= W or sy < 0 or sy >= H:
                        continue
                    if S[sy][sx] == '#':
                        continue
                    if S[sy][sx] == '.':
                        S[sy][sx] = S[y][x] + 1
                        que.append((sx,sy))
                    else:
                        if S[sy][sx] > S[y][x] + 1:
                            S[sy][sx] = S[y][x] + 1
                            que.append((sx,sy))     
    bfs(Cw-1,Ch-1)
    print(S[Dh-1][Dw-1] if S[Dh-1][Dw-1] != '.' else '-1')

if __name__ == "__main__":
    main()