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:
# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
A = [list(input()) for _ in range(H)]
B = np.zeros((H,W),dtype=int)

queue = []

for i in h:
    for j in w:
        if A[i][j]=='#':
            queue.append((i,j))

while queue!=[]:
    I,J = queue.pop(0)
    for i,j in [(I-1,J),(I+1,J),(I,J-1),(I,J+1)]:
        if (i in h) and (j in w) and A[i][j]=='.' and B[i][j]==0:
            B[i][j] = B[I][J]+1
            queue.append((i,j))

print(np.max(B))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
l=[input() for i in range(h)]
flag=[[False]*w for i in range(h)]
cost=[[0]*w for i in range(h)]
todo=deque([])
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":
            flag[i][j]=True
            todo.append([i,j])
while len(todo)>0:
    y,x=map(int,todo.popleft())
    if x!=w-1:
        if(flag[y][x+1]):
            pass
        else:
            flag[y][x+1]=True
            todo.append([y,x+1])
            cost[y][x+1]=cost[y][x]+1
    if x!=0:
        if(flag[y][x-1]):
            pass
        else:
            flag[y][x-1]=True
            todo.append([y,x-1])
            cost[y][x-1]=cost[y][x]+1
    if y!=h-1:
        if(flag[y+1][x]):
            pass
        else:
            flag[y+1][x]=True
            todo.append([y+1,x])
            cost[y+1][x]=cost[y][x]+1
    if y!=0:
        if(flag[y-1][x]):
            pass
        else:
            flag[y-1][x]=True
            todo.append([y-1,x])
            cost[y-1][x]=cost[y][x]+1
ans=0
for i in range(h):
    ans=max(ans,max(cost[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
A = [list(input()) for _ in range(H)]

queue,new_queue = [],[]

for i in h:
    for j in w:
        if A[i][j]=='#':
            queue.append((i,j))
            
def darker(i,j):
    if (i in h) and (j in w) and A[i][j]=='.':
        A[i][j]='#'
        new_queue.append((i,j))

ans = 0

while True:
    new_queue = []
    for i,j in queue:
        darker(i-1,j)
        darker(i+1,j)
        darker(i,j-1)
        darker(i,j+1)
    if new_queue==[]:
        break
    ans += 1
    queue = new_queue 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# A - Darker and Darker
import numpy as np

H,W = map(int,input().split())
h,w = np.arange(H,dtype=int),np.arange(W,dtype=int)
A = [list(input()) for _ in range(H)]

queue = []
new_queue = []

for i in h:
    for j in w:
        if A[i][j]=='#':
            queue.append((i,j))
            
def darker(i,j):
    if (i in h) and (j in w) and A[i][j]=='.':
        A[i][j]='#'
        new_queue.append((int(i),int(j)))

ans = 0

while True:
    new_queue = []
    for i,j in queue:
        darker(i-1,j)
        darker(i+1,j)
        darker(i,j-1)
        darker(i,j+1)
    if new_queue==[]:
        break
    ans += 1
    queue = new_queue 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import  deque
h,w = map(int,input().split())
mp = []
for _ in range(h):
    row = list(input())
    mp.append(row)

q = deque()
dist = [[-1] * w for _ in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '#':
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while q:
    now_x,now_y = q.popleft()
    ans = dist[now_x][now_y]
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now_x + x
        next_y = now_y + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = ans + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import  deque
h,w = map(int,input().split())
mp = []
for _ in range(h):
    row = list(input())
    mp.append(row)

q = deque()
dist = [[-1] * w for _ in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '#':
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while q:
    now = q.popleft()
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now[0] + x
        next_y = now[1] + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = dist[now[0]][now[1]] + 1
                ans = max(ans,dist[next_x][next_y])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import  deque
h,w = map(int,input().split())
mp = []
for _ in range(h):
    row = list(input())
    mp.append(row)

q = deque()
dist = [[-1] * w for i in range(h)]

for col in range(h):
    for row in range(w):
        if mp[col][row] == '#':
            q.append((col,row))
            dist[col][row] = 0
ans = 0
while len(q) != 0:
    now = q.popleft()
    for x,y in ((1,0), (0,1), (-1,0), (0,-1)):
        next_x = now[0] + x
        next_y = now[1] + y
        if 0 <= next_x < h and 0 <= next_y < w :
            if mp[next_x][next_y] == '.' and dist[next_x][next_y] < 0:
                q.append((next_x, next_y))
                dist[next_x][next_y] = dist[now[0]][now[1]] + 1
                ans = max(ans,dist[next_x][next_y])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[-1] * W for _ in range(H)]

ans = 0
que = deque([])
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            visited[i][j] = 0
            for di, dj in move:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W \
                   and S[ni][nj] != '#' and visited[ni][nj] == -1:
                    que.append((ni, nj, 1))
                    visited[ni][nj] = 1
                    ans = 1

while que:
    i, j, d = que.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == -1:
            que.append((ni, nj, d+1))
            visited[ni][nj] = d+1
            ans = d+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())

as_ = []
for i in range(h):
    a = [s for s in input().split()]
    for a_ in a:
        as_.append(a_)

ds = [[None]*w for _ in range(h)]
# ds = [[None]*w]*h ←これだとうまくいかないので注意

starts = deque()
for i, a in enumerate(as_):
    for j, a_ in enumerate(a):
        if a_ == "#":
            ds[i][j] = 0
            starts.append((i,j))
def bfs(starts, ds):
    d = 0
    while starts:
        i, j = starts.popleft()
        d = ds[i][j]
        for mx, my in [(0,1),(1,0),(-1,0),(0,-1)]:
            ni = i + my
            nj = j + mx
            if 0 <= ni < h and 0 <= nj < w:
                if ds[ni][nj] == None:
                    ds[ni][nj] = d + 1
                    starts.append((ni, nj))
    return d
d = bfs(starts, ds)
print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


h, w = MI()

a = [["#"] * (w + 2)]
for i in range(h):
    a.append(["#"] + list(S()) + ["#"])
a.append(["#"] * (w + 2))


dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))


q = set()
for x in range(1, h + 1):
    for y in range(1, w + 1):
        if a[x][y] == "#":
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if a[nx][ny] == ".":
                    q.add((nx, ny))


step = 0
while q:
    qq = set()
    step += 1
    for x, y in q:
        a[x][y] = "#"
    for x, y in q:
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if a[nx][ny] == ".":
                qq.add((nx, ny))
    q = qq

print(step)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np
from collections import Counter, defaultdict, deque

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


inf = float("inf")
mod = 10 ** 9 + 7

h, w = MI()

a = [["#"] * (w + 2)]
for i in range(h):
    a.append(["#"] + list(S()) + ["#"])
a.append(["#"] * (w + 2))


dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))


q = set()
for x in range(1, h + 1):
    for y in range(1, w + 1):
        if a[x][y] == "#":
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if a[nx][ny] == ".":
                    q.add((nx, ny))


step = 0
while q:
    qq = set()
    step += 1
    for x, y in q:
        a[x][y] = "#"
    for x, y in q:
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if a[nx][ny] == ".":
                qq.add((nx, ny))
    q = qq

print(step)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def bfs(maze, H, W):
    visited = [[-1] * W for _ in range(H)]
    q = deque([])
    for h in range(H):
        for w in range(W):
            if maze[h][w] == "#":
                visited[h][w] = 0
                q.append((h, w))

    res = 0
    while q:
        h, w = q.popleft()

        for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = h + dh
            nw = w + dw
            if 0 <= nh < H and 0 <= nw < W:
                if visited[nh][nw] == -1 and maze[nh][nw] == ".":
                    visited[nh][nw] = visited[h][w] + 1
                    if res < visited[nh][nw]:
                        res = visited[nh][nw]
                    q.append((nh, nw))

    return res


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = bfs(S, H, W)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, w = input_to_int_map()
    zone = [[s for s in input()] for i in range(h)]

    from collections import deque
    black_cell = deque()
    black_cell_pos = set()

    black_distance = [[0] * w for i in range(h)]
    for i, row in enumerate(zone):
        for j, cell in enumerate(row):
            if cell == "#":
                black_cell.append((i, j))
                black_cell_pos.add((i, j))

    while black_cell:
        black_h, black_w = black_cell.popleft()
        pre_black_distance = black_distance[black_h][black_w]
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            move_h = black_h + i
            move_w = black_w + j
            if move_h < 0 or move_w < 0 or move_h >= h or move_w >= w:
                continue
            if not (move_h, move_w) in black_cell_pos:
                black_distance[move_h][move_w] = pre_black_distance + 1
                black_cell.append((move_h, move_w))
                black_cell_pos.add((move_h, move_w))

    return max(list(map(max, black_distance)))


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    h, w = input_to_int_map()
    zone = [[s for s in input()] for i in range(h)]

    from collections import deque
    black_cell = deque()

    black_distance = [[0] * w for i in range(h)]
    for i, row in enumerate(zone):
        for j, cell in enumerate(row):
            if cell == "#":
                black_cell.append((i, j))

    while black_cell:
        black_h, black_w = black_cell.popleft()
        pre_black_distance = black_distance[black_h][black_w]
        for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            move_h = black_h + i
            move_w = black_w + j
            if move_h < 0 or move_w < 0 or move_h >= h or move_w >= w:
                continue
            if zone[move_h][move_w] == ".":
                black_distance[move_h][move_w] = pre_black_distance + 1
                black_cell.append((move_h, move_w))
                zone[move_h][move_w] = "#"

    return max(list(map(max, black_distance)))


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
h,w=map(int,input().split())
from collections import deque as que
q=que()
now=0
reached=[0 for i in range(h*w)]
for i in range(h):
    for j,v in enumerate(input()):
        if v==35:q.append((i,j));reached[w*i+j]=1;now+=1
ans=0
p=que()
for inf in range(h*w-now):
    while  len(q):
        x,y=q.pop()
        if 0<=(1+x)<h and 0<=y<w and reached[w*(1+x)+y]!=1:
            reached[w*(1+x)+y]=1
            p.append((x+1,y))
            now+=1
        if 0<=x-1<h and 0<=y<w and reached[w*(-1+x)+y]!=1:
            reached[w*(x-1)+y]=1
            p.append((x-1,y))
            now+=1
        if 0<=x<h and 0<=y+1<w and reached[w*x+y+1]!=1:
            reached[w*x+y+1]=1
            p.append((x,y+1))
            now+=1
        if 0<=x<h and 0<=y-1<w and reached[w*x+y-1]!=1:
            reached[w*x+y-1]=1
            p.append((x,y-1))
            now+=1

    ans+=1
    q,p=p,q
    if now==h*w:break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
h,w=map(int,input().split())
from collections import deque as que
q=que()
now=0
reached=[0 for i in range(h*w)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==35:q.append((i,j));reached[w*i+j]=1;now+=1
ans=0
p=que()
for inf in range(h*w-now):
    while  len(q):
        x,y=q.pop()
        if 0<=(1+x)<h and 0<=y<w and reached[w*(1+x)+y]!=1:
            reached[w*(1+x)+y]=1
            p.append((x+1,y))
            now+=1
        if 0<=x-1<h and 0<=y<w and reached[w*(-1+x)+y]!=1:
            reached[w*(x-1)+y]=1
            p.append((x-1,y))
            now+=1
        if 0<=x<h and 0<=y+1<w and reached[w*x+y+1]!=1:
            reached[w*x+y+1]=1
            p.append((x,y+1))
            now+=1
        if 0<=x<h and 0<=y-1<w and reached[w*x+y-1]!=1:
            reached[w*x+y-1]=1
            p.append((x,y-1))
            now+=1

    ans+=1
    q,p=p,q
    if now==h*w:break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
h,w=map(int,input().split())
from collections import deque as que
q=que()
now=0
reached=[0]*(h*w)
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==35:q.append((i,j));reached[w*i+j]=1;now+=1
ans=0
p=que()
for inf in range(h*w-now):
    while  len(q):
        a,s=q.pop()
        for x,y in [(a+1,s),(a-1,s),(a,s+1),(a,s-1)]:
            if 0<=x<h and 0<=y<w and reached[w*x+y]!=1:
                reached[w*x+y]=1
                p.append((x,y))
                now+=1
    ans+=1
    q,p=p,q
    if now==h*w:break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
h,w=map(int,input().split())
from collections import deque as que

q=que()
now=0
reached=[[0]*w for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==35:q.append((i,j));reached[i][j]=1;now+=1
ans=0
p=que()
for inf in range(h*w-now):
    while  len(q):
        a,s=q.pop()
        for x,y in [(a+1,s),(a-1,s),(a,s+1),(a,s-1)]:
            if 0<=x<h and 0<=y<w and reached[x][y]!=1:
                reached[x][y]=1
                p.append((x,y))
                now+=1
    ans+=1
    q,p=p,q
    if now==h*w:break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
h,w=map(int,input().split())
from collections import deque as que
q=que()
now=0
reached=[[0]*w for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==35:q.append((i,j));reached[i][j]=1;now+=1
ans=0
p=que()
for inf in range(h*w-now):
    while  len(q):
        a,s=q.pop()
        for x,y in [(a+1,s),(a-1,s),(a,s+1),(a,s-1)]:
            if 0<=x<h and 0<=y<w and reached[x][y]!=1:
                reached[x][y]=1
                p.append((x,y))
                now+=1
    ans+=1
    q=p
    p=que()
    if now==h*w:break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
h,w=map(int,input().split())
from queue import Queue as que
q=que()
now=0
reached=[[0]*w for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==35:q.put((i,j));reached[i][j]=1;now+=1
ans=0
p=que()
for inf in range(h*w-now):
    while not q.empty():
        a,s=q.get()
        for x,y in [(a+1,s),(a-1,s),(a,s+1),(a,s-1)]:
            if 0<=x<h and 0<=y<w and reached[x][y]!=1:
                reached[x][y]=1
                p.put((x,y))
                now+=1
    ans+=1
    q=p
    p=que()
    if now==h*w:break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
from queue import Queue as que
q=que()
now=0
reached=[[0]*w for i in range(h)]
for i in range(h):
    for j,v in enumerate(input()):
        if v=="#":q.put((i,j));reached[i][j]=1;now+=1
move=[(0,-1),(0,1),(1,0),(-1,0)]
ans=0
p=que()
while now!=h*w:
    while not q.empty():
        a,s=q.get()
        for dx,dy in move:
            if 0<=a+dx<h and 0<=s+dy<w and reached[a+dx][s+dy]!=1:
                reached[a+dx][s+dy]=1
                p.put((a+dx,s+dy))
                now+=1
    ans+=1
    p,q=que(),p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = [int(_) for _ in input().split()]
G = [list(input()) for _ in range(h)]

que = deque()
for i in range(h):
    for j in range(w):
        if G[i][j] == '#':
            que.append((i, j, 0))
cnt = 0
while que:
    i, j, c = que.popleft()

    for ni, nj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if i + ni < 0 or j + nj < 0: continue
        if i + ni >= h or j + nj >= w: continue

        if G[i + ni][j + nj] == '.':
            G[i + ni][j + nj] = '#'
            que.append((i + ni, j + nj, c + 1))
            cnt = max(cnt, c + 1)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    h,w=map(int,input().split())
    B=[[-1]*w for _ in range(h)]
    ans=0
    que=deque()
    for i in range(h):
        s=input()
        for j,ss in enumerate(s):
            if ss=="#":
                que.append((i,j))
                B[i][j]=0
    while que:
        qr,qc=que.popleft()
        for r,c in ((qr+1,qc),(qr-1,qc),(qr,qc+1),(qr,qc-1)):
            if r>=0 and r<=h-1 and c>=0 and c<=w-1 and B[r][c]==-1:
                B[r][c]=B[qr][qc]+1
                que.append((r,c))
    print(max([max(b) for b in B]))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
# '#'の地点をスタートとしてqueに全部入れる
# その際にseenもかねたdist配列を-1で初期化して，スタート地点だけ0にする，（-1のところは未踏）
# タプルでqueに入れると少し早くなるらしい
que = deque()
dist = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            que.append((y, x))
            dist[y][x] = 0

while len(que) > 0:
    # 現在地点の座標と距離を取得
    now_y, now_x = que.popleft()
    now_d = dist[now_y][now_x]
    for dy, dx in ((1,0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                # もしまだ見ていない地点ならqueに追加し，distを現在の距離+1に更新する
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_d + 1

print(now_d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
C = [list(input()) for _ in range(h)]
# '#'の地点をスタートとしてqueに全部入れる
# その際にseenもかねたdist配列を-1で初期化して，スタート地点だけ0にする，（-1のところは未踏）
# タプルでqueに入れると少し早くなるらしい
que = deque()
dist = [[-1] * w for _ in range(h)]
for y in range(h):
    for x in range(w):
        if C[y][x] == '#':
            que.append((y, x))
            dist[y][x] = 0

while len(que) > 0:
    # 現在地点の座標と距離を取得
    now_y, now_x = que.popleft()
    now_d = dist[now_y][now_x]
    for dy, dx in ((1,0), (-1, 0), (0, 1), (0, -1)):
        next_y = now_y + dy
        next_x = now_x + dx
        if 0 <= next_y < h and 0 <= next_x < w:
            if dist[next_y][next_x] == -1:
                # もしまだ見ていない地点ならqueに追加し，distを現在の距離+1に更新する
                que.append((next_y, next_x))
                dist[next_y][next_x] = now_d + 1

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, dist[y][x])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

#右上左下
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


ans = 0

que = deque()

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

def check(field):
    flag = False
    for i in range(H):
        if "." in field[i]:
            flag = True

    return flag

def one_bsf():
    global que
    global ans

    for _ in range(len(que)):
        n = que.popleft()
        ny = n[0]
        nx = n[1]

        for i in range(4):
            nny = ny + dy[i]
            nnx = nx + dx[i]

            if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                continue

            elif field[nny][nnx] == ".":
                field[nny][nnx] = "#"
                que.append((nny, nnx))

    ans += 1

while check(field):
    one_bsf()
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
field = tuple([input() for _ in range(H)])

#右上左下
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]


#(sy, sx)に一番近いところを探す
def bsf(sy, sx):

    if field[sy][sx] == "#":
        return 0
    
    else:
        dist = [[-1 for x in range(W)] for y in range(H)]
        que = deque()
        que.append((sy, sx))
        dist[sy][sx] = 0

        while len(que):
            n = que.popleft()
            ny = n[0]
            nx = n[1]

            for i in range(4):
                nny = ny + dy[i]
                nnx = nx + dx[i]

                if nny < 0 or nny >= H or nnx < 0 or nnx >= W:
                    continue

                elif field[nny][nnx] == "." and dist[nny][nnx] == -1:
                    dist[nny][nnx] = dist[ny][nx] + 1
                    que.append((nny, nnx))

                elif field[nny][nnx] == "#":
                    return dist[ny][nx] + 1

l = []

for i in range(H):
    for j in range(W):
        l.append(bsf(i, j))

print(max(l))

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys
input = sys.stdin.readline
def main():
    q = queue.Queue()
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        a[i+k[0]][j+k[1]]="0"
                        q.put([i+k[0],j+k[1],1])
    ans=0
    while not q.empty():
        v=q.get()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                a[v[0]+k[0]][v[1]+k[1]]="0"
                q.put([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy

h, w = map(int, input().split())
G = []
for i in range(h):
  g = list(input())
  G.append(g)
  
dist = [[0]*w for _ in range(h)]
S = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

for i in range(h):
  for j in range(w):
    if G[i][j] == '#':
      que.append([j, i])
      dist[i][j] = 1

ans = -1
while que:
  qq = deque()
  ans += 1
  for x, y in que:
    if y>0 and dist[y-1][x]==0:
      dist[y-1][x] = 1
      qq.append([x, y-1])
    if y<h-1 and dist[y+1][x]==0:
      dist[y+1][x] = 1
      qq.append([x, y+1])
    if x>0 and dist[y][x-1]==0:
      dist[y][x-1] = 1
      qq.append([x-1, y])
    if x<w-1 and dist[y][x+1] == 0:
      dist[y][x+1] = 1
      qq.append([x+1, y])
      
  que = qq
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
G = []
for i in range(h):
  g = list(input())
  G.append(g)
  
dist_ans = [[10**10]*w for _ in range(h)]
S = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

for i in range(h):
  for j in range(w):
    if G[i][j] == '#':
      S.append([j, i])
      
def bfs(sx, sy, dist_ans):
  dist = [[-1]*w for _ in range(h)]
  que = deque()
  que.append([sx, sy])
  dist[sy][sx] = 0
  
  while que:
    x, y = que.popleft()
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx>=0 and nx<w and ny>=0 and ny<h and G[ny][nx]!='#':
        if dist[ny][nx]==-1:
          que.append([nx, ny])
          dist[ny][nx] = dist[y][x] + 1
          dist_ans[ny][nx] = min(dist_ans[ny][nx], dist[ny][nx])
          
for sx, sy in S:
  bfs(sx, sy, dist_ans)
  dist_ans[sy][sx] = 0
  
ans = 0
for i in range(h):
  m = max(dist_ans[i])
  ans = max(m, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.ndimage.interpolation import shift
h, w = map(int, input().split())
a = np.array([[c == "#" for c in input()] for _ in range(h)], dtype=bool)
cnt = 0
while a.all() == False:
    a += shift(a, [0, -1], order=1, cval=False) \
        + shift(a, [0, 1], order=1, cval=False) \
        + shift(a, [1, 0], order=1, cval=False) \
        + shift(a, [-1, 0], order=1, cval=False)
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.ndimage.interpolation import shift
h, w = map(int, input().split())
a = np.array([[c == "#" for c in input()] for _ in range(h)], dtype=bool)
cnt = 0
while a.all() == False:
    a = a + shift(a, [0, -1], order=1, cval=False) \
        + shift(a, [0, 1], order=1, cval=False) \
        + shift(a, [1, 0], order=1, cval=False) \
        + shift(a, [-1, 0], order=1, cval=False)
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]  # 黒ならdist[i][j]は0、白なら-1

black_cells = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black_cells.append((i, j))
            dist[i][j] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        h_black, w_black = black_cells.popleft()
        d=dist[h_black][w_black]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h_black+dy
            new_w = w_black+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 max(sum(dist,[]))

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

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 dy, dx 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:
from collections import deque

h, w = map(int, input().split())
cm = [[0 for j in range(w + 2)] for i in range(h + 2)]
que = deque([])
for i in range(1, h + 1):
    s = input()
    for j in range(1, w + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
        else:
            que.append(i)
            que.append(j)
ans = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    ans = cm[y][x] + 1
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = ans
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = ans
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = ans
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = ans
        que.append(y)
        que.append(x - 1)
print(ans - 1)