Problem p02803 (python)

Fixed submission:
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S_ = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
for i, j in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S_[i][j] == '.':
        S = copy.deepcopy(S_)
        S[i][j] = '#'
        q = collections.deque([(i, j, 0)])
        while q:
            x, y, d = q.popleft()
            for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                if S[x + dx][y + dy] == '.':
                    X, Y = x + dx, y + dy
                    S[X][Y] = '#'
                    q += [(X, Y, d + 1)]
        ans = max(d, ans)
print(ans)

Buggy submission (verdict: Runtime Error):
import collections
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

H, W, *S = open(0).read().split()
H, W = [int(_) for _ in [H, W]]
A = []
B = []
C = []
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                A += [i]
                B += [nx * W + ny]
                C += [1]
print(int(np.max(floyd_warshall(csr_matrix((C, (A, B)), shape=(H*W, H*W))))))

Buggy submission (verdict: Runtime Error):
import collections
H, W, *S = open(0).read().split()
H,W=[int(_) for _ in [H,W]]
G = [set() for _ in range(H * W)]
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if S[nx][ny] == '.':
                G[i].add(nx * W + ny)
dist = [INF] * (H * W)
ans = 0
for s in range(H * W):
    if len(G[s]) and dist[s] != INF:
        Q = collections.deque([s])
        INF = 10 ** 10
        dist[s] = 0
        while True:
            if not Q:
                break
            i = Q.popleft()
            d = d1[i]
            for j in G[i]:
                if d1[j] != INF:
                    continue
                k = j
                d1[j] = d + 1
                Q.appendleft(j)
        d1 = [INF] * (H * W)
        d1[k] = 0
        Q = collections.deque([k])
        while True:
            if not Q:
                break
            i = Q.popleft()
            d = d1[i]
            for j in G[i]:
                if d1[j] != INF:
                    continue
                k = j
                d1[j] = d + 1
                Q.appendleft(j)
        ans = max(ans, d1[k])
print(ans)

Buggy submission (verdict: Runtime Error):
import copy, collections, itertools
H, W = [int(_) for _ in input().split()]
S = [['#'] * (W + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(H)] + [['#'] * (W + 2)]
ans = 0
def bfs(x, y, S):
    s = copy.deepcopy(S)
    q = collections.deque([(x, y, 0)])
    while q:
        x, y, d = q.popleft()
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if s[nx][ny] == '.':
                q += [[nx, ny, d + 1]]
                s[nx][ny] = '#'
    return x, y, d
for x,y in itertools.product(range(1, H + 1), range(1, W + 1)):
    if S[x][y] == '.':
        s[x][y] = '#'
        break
x, y, d = bfs(x, y, S)
x, y, d = bfs(x, y, S)
print(d)