Problem p02579 (python)

Fixed submission:
import collections

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


ncolors = 0
def paint(grid, colors):
    global ncolors
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.' and colors[y][x] == UNDEF:
                q = collections.deque()
                colors[y][x] = ncolors
                q.append((y, x))
                while q:
                    i, j = q.popleft()

                    for ii, jj in (
                        (i - 1, j),
                        (i, j - 1),
                        (i, j + 1),
                        (i + 1, j)
                    ):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
                            colors[ii][jj] = ncolors
                            q.append((ii, jj))
                ncolors += 1

paint(grid, colors)


def build(grid, colors, ncolors):
    g = [set() for _ in range(ncolors)]
    for i in range(h):
        for j in range(w):
            if colors[i][j] != UNDEF:
                for ii in range(i - 2, i + 3):
                    for jj in range(j - 2, j + 3):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                            c1 = colors[ii][jj]
                            c2 = colors[i][j]
                            assert c1 != UNDEF and c2 != UNDEF
                            g[c1].add(c2)
                            g[c2].add(c1)
    return g

g = build(grid, colors, ncolors)

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * ncolors
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in g[color]:
        if not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Buggy submission (verdict: Runtime Error):
import collections

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


color = 0
def paint(grid, colors):
    global color
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.' and colors[y][x] == UNDEF:
                q = collections.deque()
                colors[y][x] = color
                q.append((y, x))
                while q:
                    i, j = q.popleft()

                    for ii, jj in (
                        (i - 1, j),
                        (i, j - 1),
                        (i, j + 1),
                        (i + 1, j)
                    ):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
                            colors[ii][jj] = color
                            q.append((ii, jj))
                color += 1

paint(grid, colors)


def build(grid, colors, ncolors):
    g = [set() for _ in range(ncolors)]
    for i in range(h):
        for j in range(w):
            if colors[i][j] != UNDEF:
                for ii in range(i - 2, i + 3):
                    for jj in range(j - 2, j + 3):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                            c1 = colors[ii][jj]
                            c2 = colors[i][j]
                            assert c1 != UNDEF and c2 != UNDEF
                            g[c1].add(c2)
                            g[c2].add(c1)
    return g

g = build(grid, colors, color)

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * len(colors)
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in g[color]:
        if not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Buggy submission (verdict: Runtime Error):
import collections
import threading

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


def paint(grid, i, j, colors, color):
    q = collections.deque()
    colors[i][j] = color
    q.append((i, j))
    while q:
        i, j = q.popleft()

        for ii, jj in (
            (i - 1, j),
            (i, j - 1),
            (i, j + 1),
            (i + 1, j)
        ):
            if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
                colors[ii][jj] = color
                q.append((ii, jj))

color = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == '.' and colors[i][j] == UNDEF:
            paint(grid, i, j, colors, color)
            color += 1


g = [set() for _ in range(color)]
for i in range(h):
    for j in range(w):
        if colors[i][j] != UNDEF:
            for ii in range(i - 2, i + 3):
                for jj in range(j - 2, j + 3):
                    if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                        c1 = colors[ii][jj]
                        c2 = colors[i][j]
                        assert c1 != UNDEF and c2 != UNDEF
                        g[c1].add(c2)
                        g[c2].add(c1)

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * len(colors)
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in g[color]:
        if not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import collections
import threading
sys.setrecursionlimit(1000 * 1000 + 100)

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


def paint(grid, i, j, colors, color):
    colors[i][j] = color
    for ii, jj in (
        (i - 1, j),
        (i, j - 1),
        (i, j + 1),
        (i + 1, j)
    ):
        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
            paint(grid, ii, jj, colors, color)

threading.stack_size(2 ** 27)

color = 0
def recurse():
    global color
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '.' and colors[i][j] == UNDEF:
                paint(grid, i, j, colors, color)
                color += 1

t = threading.Thread(target=recurse)
t.start()
t.join()

g = [[0] * color for _ in range(color)]
for i in range(h):
    for j in range(w):
        if colors[i][j] != UNDEF:
            for ii in range(i - 2, i + 3):
                for jj in range(j - 2, j + 3):
                    if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                        c1 = colors[ii][jj]
                        c2 = colors[i][j]
                        assert c1 != UNDEF and c2 != UNDEF
                        g[c1][c2] = 1
                        g[c2][c1] = 1

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * len(colors)
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in range(len(g)):
        if g[color][other] and not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)