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


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if 0<=nv[0]<self.H and 0<=nv[1]<self.W:
                    if self.dist[nv[0]][nv[1]] != -1:
                        continue
                    self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                    self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                sv_arr.append([i,j])
    bfs.bfs(sv_arr)
    cnt = max(sum(bfs.dist,[]))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

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


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while len(self.que)>0:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if 0<=nv[0]<self.H and 0<=nv[1]<self.W:
                    if self.dist[nv[0]][nv[1]] != -1:
                        continue
                    self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                    self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                sv_arr.append([i,j])
    bfs.bfs(sv_arr)
    cnt = max(sum(bfs.dist,[]))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

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


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while len(self.que)>0:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if 0<=nv[0]<self.H and 0<=nv[1]<self.W:
                    if self.dist[nv[0]][nv[1]] != -1:
                        continue
                    self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                    self.que.append(nv)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if graph[i][j] == '#':
                sv_arr.append([i,j])
    bfs.bfs(sv_arr)
    cnt = max(sum(bfs.dist,[]))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

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


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v_arr):
        # 初期条件(0-indexed)
        for start_v in start_v_arr:
            self.dist[start_v] = 0
            self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    start_v_arr = []
    for v, val in enumerate(bfs.val):
        if val == '#':
            start_v_arr.append(v)
    bfs.bfs(start_v_arr)
    cnt = max(bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

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


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v_arr):
        # 初期条件(0-indexed)
        for start_v in start_v_arr:
            self.dist[start_v] = 0
            self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    dist = [float('inf')] * bfs.N
    start_v_arr = []
    for v, val in enumerate(bfs.val):
        if val == '#':
            start_v_arr.append(v)
    bfs.bfs(start_v_arr)
    cnt = max(bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

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


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def clear(self):
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v_arr):
        # 初期条件(0-indexed)
        for start_v in start_v_arr:
            self.dist[start_v] = 0
            self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    dist = [float('inf')] * bfs.N
    start_v_arr = []
    for v, val in enumerate(bfs.val):
        if val == '#':
            start_v_arr.append(v)
    bfs.bfs(start_v_arr)
    cnt = max(bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

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


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def clear(self):
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v):
        # 初期条件(0-indexed)
        self.dist[start_v] = 0
        self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    dist = [float('inf')] * bfs.N
    for v, val in enumerate(bfs.val):
        if val == '#':
            bfs.bfs(v)
            dist = [min(a,b) for a,b in zip(dist,bfs.dist)]
            bfs.clear()
    cnt = max(dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()

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


def grid2adj(arr_grid,direction=4):
    def cand(i,j,direction):
        if direction == 4:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]
        elif direction == 8:
            return [[i-1,j],[i+1,j],[i,j-1],[i,j+1],
                    [i-1,j-1],[i-1,j+1],[i+1,j-1],[i+1,j+1]]
        else:
            print('Error')
    
    M,N = len(arr_grid),len(arr_grid[0])
    arr_con = [[] for i in range(M*N)]
    for i in range(M):
        for j in range(N):
            v = i*N+j
            for _cand in cand(i,j,direction):
                if 0<=_cand[0]<M and 0<=_cand[1]<N:
                    next_v = _cand[0]*N+_cand[1]
                    arr_con[v].append(next_v)
    arr_val = sum(arr_grid,[])

    return arr_con, arr_val


class BFS():
    def __init__(self, con, val=None):
        # 隣接リスト表現
        self.con = con
        self.val = val
        self.N = len(self.con)
        # 始点からの距離
        self.dist = [-1]*self.N
        self.que = deque()

    def clear(self):
        self.dist = [-1]*self.N
        self.que = deque()

    def bfs(self, start_v):
        # 初期条件(0-indexed)
        self.dist[start_v] = 0
        self.que.append(start_v)

        while len(self.que)>0:
            v = self.que.popleft()
            for next_v in self.con[v]:
                if self.dist[next_v] != -1:
                    continue
                self.dist[next_v] = self.dist[v] + 1
                self.que.append(next_v)


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    g_con, g_val = grid2adj(graph)
    bfs = BFS(g_con,g_val)

    dist = [float('inf')] * bfs.N
    for v, val in enumerate(bfs.val):
        if val == '#':
            bfs.bfs(v)
            for i in range(bfs.N):
                dist[i] = min(dist[i],bfs.dist[i])
            bfs.clear()
    cnt = max(dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Fixed submission:
from sys import stdin
from collections import deque


class BFS():
    def __init__(self, grid_graph):
        # grid表現
        self.graph = grid_graph
        self.H = len(self.graph)
        self.W = len(self.graph[0])
        # 始点からの距離
        self.dist = [[-1]*self.W for i in range(self.H)]
        # キュー
        self.que = deque()

    def bfs(self, sv_arr):
        dx = [ 1, 0,-1, 0]
        dy = [ 0, 1, 0,-1]

        # 初期条件(0-indexed)
        for sv in sv_arr:
            self.dist[sv[0]][sv[1]] = 0
            self.que.append(sv)

        while self.que:
            v = self.que.popleft()
            for _dx, _dy in zip(dx,dy):
                nv = [v[0]+_dx,v[1]+_dy]
                if not 0<=nv[0]<self.H: continue 
                if not 0<=nv[1]<self.W: continue
                if self.dist[nv[0]][nv[1]] != -1: continue
                self.dist[nv[0]][nv[1]] = self.dist[v[0]][v[1]] + 1
                self.que.append(nv)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    H, W = list(map(int,_in[0].split(' ')))  # type:list(int)
    graph = []
    for i in range(H):
        _ = list(_in[i+1])  # type:list(str)
        graph.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    bfs = BFS(graph)

    sv_arr = []
    for i in range(H):
        for j in range(W):
            if bfs.graph[i][j] == '#':
                sv_arr.append([i,j])

    bfs.bfs(sv_arr)
    cnt = max(max(_) for _ in bfs.dist)
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


if __name__ == "__main__":
    main()