Problem p02579 (python)

Fixed submission:
def main():
    from collections import deque

    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y][x]:
                continue
            vis[y][x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                    continue
                if m[y + s][x + t] == '#':
                    edge.append((y, x))
                    continue
                q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh][dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                        continue
                    if vis[y + s][x + t]:
                        continue
                    if m[y + s][x + t] == '#':
                        continue
                    nx += walk(y + s, x + t)
                    if vis[dh][dw]:
                        return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(100000)

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[start[0]][start[1]] = 0
    vis = [[False] * w for _ in range(h)]

    def fill(nx, c):
        if len(nx) == 0:
            return
        q = deque(nx)
        wall = []
        while q:
            i, j = q.pop()
            cost[i][j] = c
            vis[i][j] = True
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= i + di < h and 0 <= j + dj < w:
                    if (i + di, j + dj) == goal:
                        print(c)
                        exit()
                    if vis[i + di][j + dj]:
                        continue
                    if maze[i + di][j + dj] == '#':
                        wall.append((i + di, j + dj))
                    else:
                        q.append((i + di, j + dj))

        jump(wall, c + 1)

    def jump(wall, c):
        nx = []
        q = deque(wall)
        while q:
            i, j = q.pop()
            cost[i][j] = c
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if 0 <= i + di < h and 0 <= j + dj < w:
                        if (i + di, j + dj) == goal:
                            print(c)
                            exit()
                        if vis[i + di][j + dj]:
                            continue
                        if maze[i + di][j + dj] == '.':
                            cost[i + di][j + dj] = c
                            nx.append((i + di, j + dj))

        fill(nx, c)

    fill([start], 0)
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from collections import deque
    import sys
    sys.setrecursionlimit(100000)

    h, w = map(int, input().split())
    start = tuple(map(lambda x: int(x) - 1, input().split()))
    goal = tuple(map(lambda x: int(x) - 1, input().split()))

    maze = tuple([tuple(input()) for _ in range(h)])
    cost = [[float('Inf')] * w for _ in range(h)]
    cost[start[0]][start[1]] = 0
    vis = [[False] * w for _ in range(h)]

    def fill(nx, c):
        if len(nx) == 0:
            return
        q = deque(nx)
        wall = []
        while q:
            i, j = q.pop()
            cost[i][j] = c
            vis[i][j] = True
            for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= i + di < h and 0 <= j + dj < w:
                    if (i + di, j + dj) == goal:
                        print(c)
                        exit()
                    if vis[i + di][j + dj]:
                        continue
                    if maze[i + di][j + dj] == '#':
                        wall.append((i + di, j + dj))
                    else:
                        q.append((i + di, j + dj))

        jump(wall, c + 1)

    def jump(wall, c):
        nx = []
        q = deque(wall)
        while q:
            i, j = q.pop()
            cost[i][j] = c
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    if 0 <= i + di < h and 0 <= j + dj < w:
                        if (i + di, j + dj) == goal:
                            print(c)
                            exit()
                        if vis[i + di][j + dj]:
                            continue
                        if maze[i + di][j + dj] == '.':
                            cost[i + di][j + dj] = c
                            nx.append((i + di, j + dj))

        fill(nx, c)

    fill([start], 0)
    print(-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from collections import deque
    from array import array

    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = array('u', sum([list(input()) for _ in range(h)], []))
    vis = array('b', [0] * (h * w))

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y * h + x]:
                continue
            vis[y * h + x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                    if m[(y + s) * h + x + t] == '#':
                        edge.append((y, x))
                        continue
                    q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh * h + dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if vis[(y + s) * h + x + t]:
                        continue
                    if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                        if m[(y + s) * h + x + t] == '#':
                            continue
                        nx += walk(y + s, x + t)
                        if vis[dh * h + dw]:
                            return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    sys.setrecursionlimit(100000)
    
    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j, q):
        if vis[i][j]:
            return []
        vis[i][j] = True
        q.append((i, j))

        for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                continue
            if m[i + s][j + t] == '#':
                continue
            tmp = walk(i + s, j + t, q)

        return q

    def jump(i, j, c):
        tmp = walk(i, j, [])
        if (dh, dw) in tmp:
            return c
        res = []
        for s in range(-2, 3):
            for t in range(-2, 3):
                if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                    continue
                if (i + s, j + t) in tmp:
                    continue
                if m[i + s][j + t] == '#':
                    continue

                res += walk(i + s, j + t, [])
        if (dh, dw) in res:
            return c + 1
        else:
            for i, j in res:
                tmp = jump(i, j, c + 1)
                if tmp is not None:
                    return tmp

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from collections import deque

    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j, q):
        if vis[i][j]:
            return []
        vis[i][j] = True
        q.append((i, j))

        for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                continue
            if m[i + s][j + t] == '#':
                continue
            tmp = walk(i + s, j + t, q)

        return q

    def jump(i, j, c):
        tmp = walk(i, j, [])
        if (dh, dw) in tmp:
            return c
        res = []
        for s in range(-2, 3):
            for t in range(-2, 3):
                if not 0 <= i + s <= h - 1 or not 0 <= j + t <= w - 1:
                    continue
                if (i + s, j + t) in tmp:
                    continue
                if m[i + s][j + t] == '#':
                    continue

                res += walk(i + s, j + t, [])
        if (dh, dw) in res:
            return c + 1
        else:
            for i, j in res:
                tmp = jump(i, j, c + 1)
                if tmp is not None:
                    return tmp

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(100000)
    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)]
    wall = ['#'] * (w + 2)
    s.insert(0, wall)
    s.append(wall)

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]
    group = [[0 for _ in range(w + 2)] for _ in range(h + 2)]
    gd = defaultdict(list)

    def dfs(i, j, g):
        if visited[i][j]:
            return
        visited[i][j] = True
        group[i][j] = g
        gd[g].append((i, j))
        for p, q in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            if s[i + p][j + q] == '#':
                continue
            dfs(i + p, j + q, g)

    g = 1
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if s[i][j] == '#':
                continue
            dfs(i, j, g)
            g += 1

    gstart = group[ch][cw]
    ggoal = group[dh][dw]

    visited = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def search(i, j, gfrom, step):
        visited[i][j] = True
        gij = group[i][j]
        if gij != gfrom:
            step += 1
        if gij == ggoal:
            return step
        for p in range(-2, 3):
            for q in range(-2, 3):
                if not 1 <= i + p <= h + 1:
                    continue
                if not 1 <= j + q <= w + 1:
                    continue
                if s[i + p][j + q] == '#':
                    continue
                if visited[i + p][j + q]:
                    continue
                return search(i + p, j + q, gij, step)

    g = gstart
    gs = gd[g]
    ans = float('Inf')
    if gstart == ggoal:
        print(0)
        return
    for (i, j) in gs:
        res = search(i, j, 1, 0)
        if res is not None:
            ans = min(ans, res)

    print(-1 if ans == float('Inf') else ans)


if __name__ == '__main__':
    main()