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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = deque([now])
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0
    D1 = [-W, -1, 1, W]
    D2 = []
    for dy in [-2*W, -W, 0, W, 2*W]:
        for dx in range(-2, 3):
            D2.append(dy+dx)

    while q:
        x = q.popleft()
        for d in D1:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.appendleft(x+d)
                dist[x+d] = dist[x]
    
        for d in D2:
            xx = x + d
            if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                q.append(xx)
                dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0
    D1 = [-W, -1, 1, W]
    D2 = []
    for dy in [-2*W, -W, 0, W, 2*W]:
        for dx in range(-2, 3):
            D2.append(dy+dx)

    while q:
        x = q.pop()
        for d in D1:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.append(x+d)
                dist[x+d] = dist[x]
    
        for d in D2:
            xx = x + d
            if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                q.append(xx)
                dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#' * (W+2)]
    for _ in range(H):
        S.append('#' + readline() + '#')
    S.append('#' * (W+2))
    H += 2
    W += 2
    start = ch*W + cw
    goal = dh*W + dw
    q = deque([start])
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[start] = 0
    D1 = [-W, -1, 1, W]
    D2 = []
    for dy in [-2*W, -W, 0, W, 2*W]:
        for dx in range(-2, 3):
            D2.append(dy+dx)

    while q:
        x = q.popleft()
        for d in D1:
            i, j = divmod(x+d, W)
            if S[i][j] == '.' and dist[x+d] > dist[x]:
                q.appendleft(x+d)
                dist[x+d] = dist[x]
    
        for d in D2:
            xx = x + d
            i, j = divmod(xx, W)
            if 0 <= xx < W*H and dist[xx] > dist[x] and S[i][j] == '.':
                q.append(xx)
                dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#' * (W+2)]
    for _ in range(H):
        S.append('#' + readline() + '#')
    S.append('#' * (W+2))
    H += 2
    W += 2
    start = ch*W + cw
    goal = dh*W + dw
    q = deque([start])
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[start] = 0
    D1 = [-W, -1, 1, W]
    D2 = []
    for dy in [-2*W, -W, 0, W, 2*W]:
        for dx in range(-2, 3):
            D2.append(dy+dx)

    while q:
        x = q.popleft()
        for d in D1:
            i, j = divmod(x+d, W)
            if S[i][j] == '.' and dist[x+d] > dist[x]:
                q.appendleft(x+d)
                dist[x+d] = dist[x]
    
        for d in D2:
            xx = x + d
            i, j = divmod(xx, W)
            if 0 <= xx < W*H and dist[xx] > dist[x] and S[i][j] == '.':
                q.append(xx)
                dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#' * (W+2)]
    for _ in range(H):
        S.append('#' + readline() + '#')
    S.append('#' * (W+2))
    H += 2
    W += 2
    start = ch*W + cw
    goal = dh*W + dw
    q = deque([start])
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[start] = 0
    D = [-W, -1, 1, W]
    DY = [-2*W, -W, 0, W, 2*W]

    while q:
        x = q.popleft()
        for d in D:
            i, j = divmod(x+d, W)
            if S[i][j] == '.' and dist[x+d] > dist[x]:
                q.appendleft(x+d)
                dist[x+d] = dist[x]
    
        for dy in DY:
            for dx in range(-2, 3):
                xx = x + dy + dx
                i, j = divmod(xx, W)
                if 0 <= xx < W*H and dist[xx] > dist[x] and S[i][j] == '.':
                    q.append(xx)
                    dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    start = ch*W + cw
    goal = dh*W + dw
    q = deque([start])
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[start] = 0
    D = [-W, -1, 1, W]
    DY = [-2*W, -W, 0, W, 2*W]

    while q:
        x = q.popleft()
        for d in D:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.appendleft(x+d)
                dist[x+d] = dist[x]
    
        for dy in DY:
            for dx in range(-2, 3):
                xx = x + dy + dx
                if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                    q.append(xx)
                    dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = deque([now])
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0
    D = [-W, -1, 1, W]
    DY = [-2*W, -W, 0, W, 2*W]

    while q:
        x = q.popleft()
        for d in D:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.appendleft(x+d)
                dist[x+d] = dist[x]
    
        for dy in DY:
            for dx in range(-2, 3):
                xx = x + dy + dx
                if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                    q.append(xx)
                    dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0
    D = [-W, -1, 1, W]
    DY = [-2*W, -W, 0, W, 2*W]

    while q:
        x = q.pop()
        for d in D:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.append(x+d)
                dist[x+d] = dist[x]
    
        for dy in DY:
            for dx in range(-2, 3):
                xx = x + dy + dx
                if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                    q.append(xx)
                    dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        x = q.pop()
        for d in [-W, -1, 1, W]:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.append(x+d)
                dist[x+d] = dist[x]
    
        for dy in [-2*W, -W, 0, W, 2*W]:
            for dx in range(-2, 3):
                xx = x + dy + dx
                if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                    q.append(xx)
                    dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        x = q.pop()
        for d in [-W, -1, 1, W]:
            if S[x+d] == '.' and dist[x+d] > dist[x]:
                q.append(x+d)
                dist[x+d] = dist[x]
    
        for dy in [-2*W, -W, 0, W, 2*W]:
            for dx in range(-2, 3):
                xx = x + dy + dx
                if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                    q.append(xx)
                    dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] > dist[x]:
                    q.append(x+d)
                    dist[x+d] = dist[x]
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] > dist[x]:
                    q.append(x+d)
                    dist[x+d] = dist[xs
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x] and S[xx] == '.':
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] == -1:
                    q.append(x+d)
                    dist[x+d] = dist[x]
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x]:
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

Buggy python submission (verdict: Runtime Error):
import sys


def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2
    now = ch*W + cw
    goal = dh*W + dw
    q = [now]
    inf = 999_999_999
    dist = [inf] * (H*W)
    dist[now] = 0

    while q:
        same_area = []
        while q:
            x = q.pop()
            same_area.append(x)
            for d in [-W, -1, 1, W]:
                if S[x+d] == '.' and dist[x+d] == -1:
                    q.append(x+d)
                    dist[x+d] = dist[x]
        
        for x in same_area:
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in range(-2, 3):
                    xx = x + dy + dx
                    if 0 <= xx < W*H and dist[xx] > dist[x]:
                        q.append(xx)
                        dist[xx] = dist[x] + 1
    return dist[goal] if dist[goal] != inf else -1


if __name__ == '__main__':
    ans = solve()
    print(ans)


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area.copy()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

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

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area.copy()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()


Fixed submission:
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['#'] * (W+2)
    for _ in range(H):
        S += ['#'] + list(readline().rstrip()) + ['#']
    S += ['#'] * (W+2)
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '#':
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    # print(now, goal)
    # print(uf.find(now), uf.find(goal))
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    # for i in range(H):
    #     print(S[6*i:6*i+6])
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()