Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())

grid = [[-1]*W for _ in range(H)]

queue = deque([])

ans = 0

# while True:
#     f = 0
for i in range(H):
    s = input()
    for j, ss in enumerate(s):
        if ss =="#":
            queue.append((i, j))
            grid[i][j] = 0

#黒点をスタート地点とし、上下左右に移動した時の移動距離を記録していく
while queue:
    h, w = queue.popleft()
    for i in [h-1, h+1]:
            if i >= 0 and i < H:
                if grid[i][w] == -1:
                    grid[i][w] = grid[h][w]+1
                    queue.append((i, w))
    for j in [w-1, w+1]:
        if j >= 0 and j < W:
            if grid[h][j] == -1:
                grid[h][j] = grid[h][w]+1
                queue.append((h, j))

# print(grid)
print(max([max(b) for b in grid]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())

A = [list(input()) for _ in range(H)]

queue = deque([])

cnt = 0
black = 0

while True:
    f = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                queue.append((i, j))
                black += 1
            elif A[i][j] == ".":
                f = 1

    if not f:
        break
    while queue:
        h, w = queue.popleft()
        for i in [h-1, h+1]:
                if i >= 0 and i < H:
                    if A[i][w] == ".":
                        A[i][w] = "#"
                        # queue.append((i, w))
        for j in [w-1, w+1]:
            if j >= 0 and j < W:
                if A[h][j] == ".":
                    A[h][j] = "#"
                    # queue.append((h, j))
    cnt += 1
    # print(A)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
import numpy as np
 
def my_bfs(visited, q, h, w):    
    while q:
        if visited.min() > -1:
            i, j, d = q.pop()
            return d
        i, j, d = q.popleft()
        if i > 0 and visited[i - 1][j] == -1:
            q.append((i - 1, j, d + 1))
            visited[i - 1][j] = d + 1
        if i < h - 1 and visited[i + 1][j] == -1:
            q.append((i + 1, j, d + 1))
            visited[i + 1][j] = d + 1
        if j > 0 and visited[i][j - 1] == -1:
            q.append((i, j - 1, d + 1))
            visited[i][j - 1] = d + 1
        if j < w - 1 and visited[i][j + 1] == -1:
            q.append((i, j + 1, d + 1))
            visited[i][j + 1] = d + 1
    else:
        return d


h , w = map(int, input().split())
visited = np.full((h,w), -1)
q = deque([])
for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '#':
            visited[y][x] = 0
            q.append((y, x, 0))
d = my_bfs(visited, q, h, w)
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
  h,w=map(int,input().split())
  a=[list(map(lambda x:0 if x=='#' else -1,list(input()))) for _ in range(h)]
  todo=[]
  from collections import deque
  for i in range(h):
    for j in range(w):
      if a[i][j]==0:
        todo.append([i,j])
  todo=deque(todo)
  ans=0
  while todo:
    i,j=todo.popleft()
    d=a[i][j]+1
    ans=d-1
    if i>0 and a[i-1][j]==-1:
      a[i-1][j]=d
      todo.append([i-1,j])
    if i<h-1 and a[i+1][j]==-1:
      a[i+1][j]=d
      todo.append([i+1,j])
    if j>0 and a[i][j-1]==-1:
      a[i][j-1]=d
      todo.append([i,j-1])
    if j<w-1 and a[i][j+1]==-1:
      a[i][j+1]=d
      todo.append([i,j+1])
  print(ans)
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(map(lambda x:0 if x=='#' else -1,list(input()))) for _ in range(h)]
todo=[]
from collections import deque
for i in range(h):
  for j in range(w):
    if a[i][j]==0:
      todo.append([i,j])
seen=[[0]*w for _ in range(h)]
from collections import deque
todo=deque(todo)
ans=0
while todo:
  i,j=todo.popleft()
  d=a[i][j]+1
  ans=d-1
  if i>0 and a[i-1][j]==-1:
    a[i-1][j]=d
    todo.append([i-1,j])
  if i<h-1 and a[i+1][j]==-1:
    a[i+1][j]=d
    todo.append([i+1,j])
  if j>0 and a[i][j-1]==-1:
    a[i][j-1]=d
    todo.append([i,j-1])
  if j<w-1 and a[i][j+1]==-1:
    a[i][j+1]=d
    todo.append([i,j+1])

print(ans)
#for ai in a:
#  print(ai)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(map(lambda x:int(x=='#'),list(input()))) for _ in range(h)]
todo=[]
next_todo=[]
from collections import deque
for i in range(h):
  for j in range(w):
    if a[i][j]==1:
      next_todo.append([i,j])
seen=[[0]*w for _ in range(h)]
ans=0
while next_todo:
  todo=next_todo.copy()
  next_todo=[]
  while todo:
    i,j=todo.pop()
    if i>0 and a[i-1][j]==0:
      a[i-1][j]=1
      next_todo.append([i-1,j])
    if i<h-1 and a[i+1][j]==0:
      a[i+1][j]=1
      next_todo.append([i+1,j])
    if j>0 and a[i][j-1]==0:
      a[i][j-1]=1
      next_todo.append([i,j-1])
    if j<w-1 and a[i][j+1]==0:
      a[i][j+1]=1
      next_todo.append([i,j+1])
  if next_todo:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
 
def dfs(visited, q, h, w):    
    while q:
        if not False in itertools.chain.from_iterable(visited):
            i, j, d = q.pop()
            return d
        i, j, d = q.popleft()
        if i > 0 and visited[i - 1][j] == False:
            q.append((i - 1, j, d + 1))
            visited[i - 1][j] = True
        if i < h - 1 and visited[i + 1][j] == False:
            q.append((i + 1, j, d + 1))
            visited[i + 1][j] = True
        if j > 0 and visited[i][j - 1] == False:
            q.append((i, j - 1, d + 1))
            visited[i][j - 1] = True
        if j < w - 1 and visited[i][j + 1] == False:
            q.append((i, j + 1, d + 1))
            visited[i][j + 1] = True
    else:
        return d


h , w = map(int, input().split())
visited = [[False] * w for _ in range(h)]
q = deque([])
for y in range(h):
    _in = input()
    for x, value in enumerate(_in):
        if value == '#':
            visited[y][x] = True
            q.append((y, x, 0))
d = dfs(visited, q, h, w)
print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
import sys
buf = sys.stdin.buffer
 
def dfs(field, h, w):
    visited = [[False] * w for _ in range(h)]
    q = deque([])
    for y in range(h):
        for x in range(w):
            if field[y][x] == '#':
                q.append((y, x, 0))
                visited[y][x] = True
    
    while q:
        if not False in itertools.chain.from_iterable(visited):
            i, j, d = q.pop()
            return d
        i, j, d = q.popleft()
        if i > 0 and visited[i - 1][j] == False and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
            visited[i - 1][j] = True
        if i < h - 1 and visited[i + 1][j] == False and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
            visited[i + 1][j] = True
        if j > 0 and visited[i][j - 1] == False and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
            visited[i][j - 1] = True
        if j < w - 1 and visited[i][j + 1] == False and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
            visited[i][j + 1] = True
    else:
        return d


h , w = map(int,buf.readline().split())
field = [sys.stdin.readline().rstrip() for _ in range(h)]
d = dfs(field, h, w)
print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
 
def dfs(field, h, w):
    visited = [[False] * w for _ in range(h)]
    q = deque([])
    for y in range(h):
        for x in range(w):
            if field[y][x] == '#':
                q.append((y, x, 0))
                visited[y][x] = True
    
    while q:
        if not False in itertools.chain.from_iterable(visited):
            i, j, d = q.pop()
            return d
        i, j, d = q.popleft()
        if i > 0 and visited[i - 1][j] == False and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
            visited[i - 1][j] = True
        if i < h - 1 and visited[i + 1][j] == False and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
            visited[i + 1][j] = True
        if j > 0 and visited[i][j - 1] == False and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
            visited[i][j - 1] = True
        if j < w - 1 and visited[i][j + 1] == False and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
            visited[i][j + 1] = True
    else:
        return d


h , w = map(int, input().split())
field = [input() for _ in range(h)]
dot_cnt = sum(r.count('.') for r in field)
d = dfs(field, h, w)
print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
 
def dfs(field, h, w):
    visited = [[False] * w for _ in range(h)]
    q = deque([])
    for y in range(h):
        for x in range(w):
            if field[y][x] == '#':
                q.append((y, x, 0))
                visited[y][x] = True
    
    while q:
        i, j, d = q.popleft()
        if i > 0 and visited[i - 1][j] == False and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
            visited[i - 1][j] = True
        if i < h - 1 and visited[i + 1][j] == False and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
            visited[i + 1][j] = True
        if j > 0 and visited[i][j - 1] == False and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
            visited[i][j - 1] = True
        if j < w - 1 and visited[i][j + 1] == False and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
            visited[i][j + 1] = True
    else:
        return d


h , w = map(int, input().split())
field = [input() for _ in range(h)]
dot_cnt = sum(r.count('.') for r in field)
d = dfs(field, h, w)
print(d)

Submission status: Time Limit Exceeded

Solution code:
# ぜんぜんわからんかったので解説AC
from collections import deque
h, w = map(int, input().split())

table = [[False] * w for _ in range(h)]
queue = deque()
for i in range(h):
    line = list(input())
    for j, v in enumerate(line):
        if v == "#":
            queue.append((i, j))
            table[i][j] = True
ans = 0
steps = [0, 1, 0, -1, 0]
while len(queue) > 0:
    # ここでqueueの中身ぜんぶ抜くの頭いいな
    nex_queue = deque()
    for _ in range(len(queue)):
        g = queue.popleft()
        for i in range(4):
            nx, ny = g[1] + steps[i], g[0] + steps[i + 1]
            if 0 <= nx < w and 0 <= ny < h and table[ny][nx] == False:
                table[ny][nx] = True
                nex_queue.append((ny, nx))
    ans += 1  # よう考えたらここでよかったわ
    queue = nex_queue
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
# ぜんぜんわからんかったので解説AC
from collections import deque
h, w = map(int, input().split())

table = [[False] * w for _ in range(h)]
queue = deque()
for i in range(h):
    line = list(input())
    for j, v in enumerate(line):
        if v == "#":
            queue.append((i, j))
            table[i][j] = True
ans = 0
steps = [0, 1, 0, -1, 0]
while len(queue) > 0:
    # ここでqueueの中身ぜんぶ抜くの頭いいな
    for _ in range(len(queue)):
        g = queue.popleft()
        for i in range(4):
            nx, ny = g[1] + steps[i], g[0] + steps[i + 1]
            if 0 <= nx < w and 0 <= ny < h and table[ny][nx] == False:
                table[ny][nx] = ans + 1
                queue.append((ny, nx))
    ans += 1  # よう考えたらここでよかったわ
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
# ぜんぜんわからんかったので解説AC
from collections import deque
h, w = map(int, input().split())


class Grid:
    def __init__(self, X, Y, C):
        self.X = X
        self.Y = Y
        self.C = C


INF = 10**8
table = [[INF] * w for _ in range(h)]
queue = deque()
for i in range(h):
    line = list(input())
    for j, v in enumerate(line):
        if v == "#":
            g = Grid(X=j, Y=i, C=0)
            queue.append(g)
            table[i][j] = 0
ans = 0
steps = [0, 1, 0, -1, 0]
while len(queue) > 0:
    g = queue.popleft()
    ans = max(ans, g.C)
    for i in range(4):
        nx, ny = g.X + steps[i], g.Y + steps[i + 1]
        if 0 <= nx < w and 0 <= ny < h and table[ny][nx] == INF:
            table[ny][nx] = g.C + 1
            nexg = Grid(X=nx, Y=ny, C=g.C + 1)
            queue.append(nexg)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ぜんぜんわからんかったので解説AC
from collections import deque
h, w = map(int, input().split())


class Grid:
    def __init__(self, X, Y, C):
        self.X = X
        self.Y = Y
        self.C = C


INF = 10**8
table = [[INF] * w for _ in range(h)]
queue = deque()
for i in range(h):
    line = list(input())
    for j, v in enumerate(line):
        if v == "#":
            g = Grid(X=j, Y=i, C=0)
            queue.append(g)
            table[i][j] = 0
ans = 0
steps = [0, 1, 0, -1, 0]
while len(queue) > 0:
    g = queue.popleft()
    ans = max(ans, g.C)
    for i in range(4):
        nx, ny = g.X + steps[i], g.Y + steps[i + 1]
        if 0 <= nx < w and 0 <= ny < h and table[ny][nx] >= g.C + 1:
            table[ny][nx] = g.C + 1
            nexg = Grid(X=nx, Y=ny, C=g.C + 1)
            queue.append(nexg)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())

by,bx= deque(),deque()
Map = []
Map.append('@'*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '#'):
      Map[i+1][j] = 0
      by.append(i+1),bx.append(j)
Map.append('@'*(W+2))      

cnt = 0
while(1):
  if(len(by) == 0):
    cnt = Map[ny][nx]
    break
   
  ny,nx = by.popleft(),bx.popleft()
  vec_y,vec_x = [1,-1,0,0],[0,0,1,-1]
  for i in range(4):
      if(Map[ny+vec_y[i]][nx+vec_x[i]] == '.'):
         Map[ny+vec_y[i]][nx+vec_x[i]] = Map[ny][nx] + 1
         by.append(ny+vec_y[i]),bx.append(nx+vec_x[i])
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int,input().split())

by,bx= deque(),deque()
Map = []
Map.append('@'*(W+2))
for i in range(H):
  c = list('@'+input()+'@')
  Map.append(c)
  for j in range(W+2):
    if(c[j] == '#'):
      Map[i+1][j] = 0
      by.append(i+1),bx.append(j)
Map.append('@'*(W+2))      

cnt = 0
while(1):
  if(len(by) == 0):
    break
   
  ny,nx = by.popleft(),bx.popleft()
  vec_y,vec_x = [1,-1,0,0],[0,0,1,-1]
  for i in range(4):
      if(Map[ny+vec_y[i]][nx+vec_x[i]] == '.'):
         Map[ny+vec_y[i]][nx+vec_x[i]] = Map[ny][nx] + 1
         cnt = max(cnt, Map[ny][nx] + 1) 
         by.append(ny+vec_y[i]),bx.append(nx+vec_x[i])
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())

queue=[]
mat=[[True]*(W+2)]
for i in range(1,H+1):
  array=[True]+[x=="#" for x in input()]+[True]
  mat.append(array)
  for j in range(1,W+1):
    if array[j]:
      queue.append((i,j))
mat.append([True]*(W+2))
#print(mat)
#print(queue)

d=0
while queue:
  new_queue=set()
  for q in queue:
    i,j=q
    #print(q)
    if not mat[i-1][j]:
      new_queue.add((i-1,j))
      mat[i-1][j]=True
    if not mat[i+1][j]:
      new_queue.add((i+1,j))
      mat[i+1][j]=True
    if not mat[i][j-1]:
      new_queue.add((i,j-1))
      mat[i][j-1]=True
    if not mat[i][j+1]:
      new_queue.add((i,j+1))
      mat[i][j+1]=True
      
  queue=list(new_queue)
  d+=1
  
print(d-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int,input().split())
grid=[input() for i in range(H)]
dist=[[-1]*W for _ in range(H)]

black_cells=deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == "#":
            black_cells.append((h,w))
            dist[h][w]=0

def bfs(black_cells,dist):
        d=0
        while black_cells:
            h,w=black_cells.popleft()
            d=dist[h][w]
            for dx, dy in ((1,0),(0,1),(-1,0),(0,-1)):
                new_h=h+dy
                new_w=w+dx
                if new_h <0 or H <= new_h or new_w < 0 or W<=new_w:
                    continue
                if dist[new_h][new_w]==-1:
                    dist[new_h][new_w]=d+1
                    black_cells.append((new_h,new_w))
        return d

d=bfs(black_cells,dist)
print(d)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int, input().split())
F=[]
for h in range(H):
    a=list(input())
    F.append(a)

black=[]
white=[]
for h in range(H):
    for w in range(W):
        if F[h][w]=="#":
            black.append([h,w])
        else:
            white.append([h,w])
black=np.array(black)
white=np.array(white)
ans=0
#print(black, white)
for i in range(white.shape[0]):
    w=white[i,:].reshape(1,2)
    
    sub=np.abs(black-w).sum(axis=1).min()
    
    ans=max(sub, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
from sys import stdin
field = []
bque = []
for i in range(H):
    st = stdin.readline()[:-1]
    ls = []
    for j,ss in enumerate(st):
        ls.append(ss)
        if ss=='#':
            bque.append([i,j])

    field.append(ls)

from collections import deque

que = deque([])
que.append(bque)
count = 0
while len(que)>0:
    ll = que.popleft()
    nls = []
    for item in ll:
        x = item[0]
        y = item[1]
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=x+dx<=H-1:
                    if field[x+dx][y]=='.':
                        field[x+dx][y]='#'
                        nls.append([x+dx,y])
                if 0<=y+dy<=W-1:
                    if field[x][y+dy]=='.':
                        field[x][y+dy]='#'
                        nls.append([x,y+dy])
    if len(nls) != 0:
        que.append(nls)
        count += 1
print(count)
"""微妙に遅かった60msぐらい　"""

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
field = []
bque = []
for i in range(H):
    st = str(input())
    ls = []
    for j,ss in enumerate(st):
        ls.append(ss)
        if ss=='#':
            bque.append([i,j])

    field.append(ls)

from collections import deque

que = deque([])
que.append(bque)
count = 0
while len(que)>0:
    ll = que.popleft()
    nls = []
    for item in ll:
        x = item[0]
        y = item[1]
        for dx in [-1,1]:
            for dy in [-1,1]:
                if 0<=x+dx<=H-1:
                    if field[x+dx][y]=='.':
                        field[x+dx][y]='#'
                        nls.append([x+dx,y])
                if 0<=y+dy<=W-1:
                    if field[x][y+dy]=='.':
                        field[x][y+dy]='#'
                        nls.append([x,y+dy])
    if len(nls) != 0:
        que.append(nls)
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)] # #.のグリッドの場合
#print(a)

from collections import deque
step = [(0,1), (0,-1), (1,0), (-1,0)]
que = deque()

seen = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            seen[i][j] = 0
ans = 0
#import numpy as np
#print(np.array(seen))
while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if a[xi][yi] == '#':
            continue
        if a[xi][yi] == '.':
            seen[xi][yi] = seen[x][y] + 1
            ans = max(ans, seen[xi][yi])
            a[xi][yi] = '#'
            que.append((xi, yi))
    #print(np.array(seen))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)] # #.のグリッドの場合
#print(a)

from collections import deque
step = [(0,1), (0,-1), (1,0), (-1,0)]
que = deque()

seen = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            seen[i][j] = 0
ans = 0
import numpy as np
#print(np.array(seen))
while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if a[xi][yi] == '#':
            continue
        if a[xi][yi] == '.':
            seen[xi][yi] = seen[x][y] + 1
            ans = max(ans, seen[xi][yi])
            a[xi][yi] = '#'
            que.append((xi, yi))
    #print(np.array(seen))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
M = []
for i in range(H):
    M.append(list(input()))

Bs = []
for i in range(H):
    for j in range(W):
        if M[i][j]=="#":
            Bs.append([i,j])

from collections import deque
memo = [[float("inf")] * W for i in range(H)]
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
que = deque([])
que.append(Bs)
for Bi,Bj in Bs:
    memo[Bi][Bj] = 0

out = 0
while que:
    ps = que.popleft()
    next = []
    for p in ps:
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            if (0<=nx<W)and(0<=ny<H)and(memo[ny][nx]==float("inf")):
                next.append((ny, nx))
                memo[ny][nx] = memo[p[0]][p[1]] + 1
                if memo[ny][nx]>out:
                    out=memo[ny][nx]
    if len(next)>0:
        que.append(next)

print(out)