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:
import queue

def getlist():
	return list(map(int, input().split()))

#初期化
H, W = getlist()
AL = []
for i in range(H):
	AL.extend(list(input()))


#BFS初期化
visit = [0] * (H * W)
time = [0] * (H * W)
q = queue.Queue()
for i in range(H * W):
	if AL[i] == "#":
		q.put(i)
		visit[i] = 1

while not q.empty():
	v = q.get()
	if v % W != 0:
		if visit[v - 1] != 1:
			q.put(v - 1)
			time[v - 1] = time[v] + 1
			visit[v - 1] = 1
	if v % W != W - 1:
		if visit[v + 1] != 1:
			q.put(v + 1)
			time[v + 1] = time[v] + 1
			visit[v + 1] = 1
	if W < v:
		if visit[v - W] != 1:
			q.put(v - W)
			time[v - W] = time[v] + 1
			visit[v - W] = 1
	if v < (H - 1) * W :
		if visit[v + W] != 1:
			q.put(v + W)
			time[v + W] = time[v] + 1
			visit[v + W] = 1

print(max(time))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = []
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.append((i, j))
            pass

for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = list()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.append((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.append((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.append((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.append((x, y + 1))

        d = d2

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = set()
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.add((i, j))
            pass

c = 0
for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = set()
        for x, y in d:
            c += 1
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.add((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.add((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.add((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.add((x, y + 1))

        d = d2

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = set()
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.add((i, j))
            pass

for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = set()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.add((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.add((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.add((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.add((x, y + 1))

        d = d2

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      q.append((i,j))
      lis[i][j]=0


while q:
  cur=q.popleft()
  i,j=cur[0],cur[1]

  if 0<=i+1<=h-1 and 0<=j<=w-1:
    if lis[i+1][j]==-1:
      lis[i+1][j]=lis[i][j]+1
      q.append((i+1,j))
  
  if 0<=i-1<=h-1 and 0<=j<=w-1:
    if lis[i-1][j]==-1:
      lis[i-1][j]=lis[i][j]+1
      q.append((i-1,j))

  
  if 0<=i<=h-1 and 0<=j+1<=w-1:
    if lis[i][j+1]==-1:
      lis[i][j+1]=lis[i][j]+1
      q.append((i,j+1))
      
  if 0<=i<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[i][j-1]==-1:
      lis[i][j-1]=lis[i][j]+1
      q.append((i,j-1))      
  
print(max(max(l) for l in lis))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w=map(int,input().split())
a=[input() for i in range(h)]
lis=[[-1 for i in range(w)] for j in range(h)]
q=deque()


for i in range(h):
  for j in range(w):
    if a[i][j]=="#":
      q.append((i,j))
      lis[i][j]=0


while q:
  cur=q.popleft()

  if 0<=cur[0]+1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]+1][cur[1]]==-1:
      lis[cur[0]+1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]+1,cur[1]))
  
  if 0<=cur[0]-1<=h-1 and 0<=cur[1]<=w-1:
    if lis[cur[0]-1][cur[1]]==-1:
      lis[cur[0]-1][cur[1]]=lis[cur[0]][cur[1]]+1
      q.append((cur[0]-1,cur[1]))

  
  if 0<=cur[0]<=h-1 and 0<=cur[1]+1<=w-1:
    if lis[cur[0]][cur[1]+1]==-1:
      lis[cur[0]][cur[1]+1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]+1))
      
  if 0<=cur[0]<=h-1 and 0<=cur[1]-1<=w-1:
    if lis[cur[0]][cur[1]-1]==-1:
      lis[cur[0]][cur[1]-1]=lis[cur[0]][cur[1]]+1
      q.append((cur[0],cur[1]-1))      
  
print(max(max(l) for l in lis))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
q = []
for i in range(H):
  As = list(input())
  A.append(As)
  for j in range(W):
    if A[i][j] == "#":
      q.append((i, j))
r = 0
while q:
  q2 = []
  for i, j in q:
    if i-1 >= 0 and A[i-1][j] == ".":
      A[i-1][j] = "#"
      q2.append((i-1, j))
    if i+1 < H and A[i+1][j] == ".":
      A[i+1][j] = "#"
      q2.append((i+1, j))
    if j-1 >= 0 and A[i][j-1] == ".":
      A[i][j-1] = "#"
      q2.append((i, j-1))
    if j+1 < W and A[i][j+1] == ".":
      A[i][j+1] = "#"
      q2.append((i, j+1))
  q = q2
  r += 1
r -= 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int,input().split())
graph = []
finishied = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1,-1]
x = [1,-1, 0, 0]
q = deque([])
for i in range(h):
    a = input()
    graph.append(list(a))
    for j in range(w):
        if a[j] == "#":
            q.append((i,j,0))
while q:
    c = q.popleft()
    for i in range(4):
        nh = c[0]+y[i]
        nw = c[1]+x[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or graph[nh][nw] == "#":continue
        graph[nh][nw] = "#"
        q.append((nh,nw,c[2]+1))
print(c[2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int,input().split())
graph = [list(input()) for _ in range(h)]
finishied = [[False for _ in range(w)] for _ in range(h)]
y = [0, 0, 1,-1]
x = [1,-1, 0, 0]
q = deque([])
for i in range(h):
    for j in range(w):
        if graph[i][j] == "#":
            q.append((i,j,0))
while q:
    c = q.popleft()
    for i in range(4):
        nh = c[0]+y[i]
        nw = c[1]+x[i]
        if nh < 0 or nh >= h or nw < 0 or nw >= w or graph[nh][nw] == "#":continue
        graph[nh][nw] = "#"
        q.append((nh,nw,c[2]+1))
print(c[2])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
 
q=deque()
 
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
 
dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0
 
while q:
    nq=deque()
    while True:
        y,x=q.popleft()    
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<h and 0<=nx<w and a[ny][nx]!='#':
                a[ny][nx]='#'
                nq.append((ny,nx))

        if not q:
            ans+=1
            q=nq
            break
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
field=[[False for i in range(w)] for j in range(h)]
 
q=deque()
 
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            field[i][j]=True
 
dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0
 
while q:
    nq=deque()
    while True:
        y,x=q.popleft()    
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if 0<=ny<h and 0<=nx<w and field[ny][nx]==False:
                field[ny][nx]=True
                nq.append((ny,nx))

        if not q:
            ans+=1
            q=nq
            break
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
field=[[float('inf') for i in range(w)] for j in range(h)]

q=deque()

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

dx=[1,0,-1,0]            
dy=[0,1,0,-1]
ans=0

while q:
    y,x=q.popleft()    
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if 0<=ny<h and 0<=nx<w and field[ny][nx]==float('inf'):
            field[ny][nx]=field[y][x]+1
            q.append((ny,nx))
            ans=max(ans,field[ny][nx])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())

a = [[False]*(w+2)]
for y in range(h):
    a += [[False] + [x!='#' for x in input()] + [False]]
a += [[False]*(w+2)]

s = deque()
for i in range(1, h+1):
    for j in range(1, w+1):
        if not a[i][j]:
            s.append((i,j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

a = [[False]*(w+2)]
for y in _in[1:]:
    a += [[False] + [x!='#' for x in y.replace('\n','')] + [False]]
a += [[False]*(w+2)]

s = deque()
for i in range(1, h+1):
    for j in range(1, w+1):
        if not a[i][j]:
            s.append((i,j))

ans = -1
while s:
    ns = deque()
    for i, j in s:
        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i+1,j+1))

a = [[False]*(w+2)]
a += [[False] + [True]*w + [False] for _ in range(h)]
a += [[False]*(w+2)]

ans = -1
while s:
    ns = deque()
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i+1,j+1))

a = [[False]*(w+2)]
a += [[False] + [True]*w + [False] for _ in range(h)]
a += [[False]*(w+2)]

ans = -1
while s:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            a[i-1][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i+1][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j-1] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j+1] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i+1,j+1))

a = [[False]*(w+2)]
a += [[False] + [True]*w + [False] for _ in range(h)]
a += [[False]*(w+2)]

ans = -1
while s:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            a[i][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i+1,j+1))

a = [[False]*(w+2)]
a += [[False] + [True]*w + [False] for _ in range(h)]
a += [[False]*(w+2)]

ans = 0
while True:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            ns.append((i-1, j))
        if a[i+1][j]:
            ns.append((i+1, j))
        if a[i][j-1]:
            ns.append((i, j-1))
        if a[i][j+1]:
            ns.append((i, j+1))
        
    if not ns:
        break
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j))

a = [[True]*w + [False] for _ in range(h)]
a.append([False]*(w+1))

ans = 0
while True:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            ns.append((i-1, j))
        if a[i+1][j]:
            ns.append((i+1, j))
        if a[i][j-1]:
            ns.append((i, j-1))
        if a[i][j+1]:
            ns.append((i, j+1))
        
    if not ns:
        break
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j))

a = [[True]*w for _ in range(h)]

ans = 0
while True:
    ns = deque()
    for i, j in s:
        a[i][j] = False

        if i>0 and a[i-1][j]:
            ns.append((i-1, j))
        if i<h-1 and a[i+1][j]:
            ns.append((i+1, j))
        if j>0 and a[i][j-1]:
            ns.append((i, j-1))
        if j<w-1 and a[i][j+1]:
            ns.append((i, j+1))
        
    if not ns:
        break
    s = ns
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j,0))

a = [[False]*w for _ in range(h)]

while s:
    i,j,k = s.popleft()
    if a[i][j]:
        continue
    
    a[i][j] = True
    ans = k
    
    if i>0:
        s.append((i-1, j, k+1))
    if i<h-1:
        s.append((i+1, j, k+1))
    if j>0:
        s.append((i, j-1, k+1))
    if j<w-1:
        s.append((i, j+1, k+1))
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j,0))

a = [[True]*w for _ in range(h)]

while s:
    q = s.popleft()
    
    a[q[0]][q[1]] = False
    ans = q[2]
    
    if q[0]>0 and a[q[0]-1][q[1]]:
        s.append((q[0]-1, q[1], q[2]+1))
    if q[0]<h-1 and a[q[0]+1][q[1]]:
        s.append((q[0]+1, q[1], q[2]+1))
    if q[1]>0 and a[q[0]][q[1]-1]:
        s.append((q[0], q[1]-1, q[2]+1))
    if q[1]<w-1 and a[q[0]][q[1]+1]:
        s.append((q[0], q[1]+1, q[2]+1))
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = deque()
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j,0))

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

while s:
    q = s.popleft()
    if a[q[0]][q[1]] != -1:
        continue
    
    a[q[0]][q[1]] = q[2]
    ans = q[2]
    
    if q[0]>0:
        s.append((q[0]-1, q[1], q[2]+1))
    if q[0]<h-1:
        s.append((q[0]+1, q[1], q[2]+1))
    if q[1]>0:
        s.append((q[0], q[1]-1, q[2]+1))
    if q[1]<w-1:
        s.append((q[0], q[1]+1, q[2]+1))
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i,j,0))

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

while s:
    q, s = s[0], s[1:]
    if a[q[0]][q[1]] != -1:
        continue
    
    a[q[0]][q[1]] = q[2]
    ans = q[2]
    
    if q[0]>0:
        s.append((q[0]-1, q[1], q[2]+1))
    if q[0]<h-1:
        s.append((q[0]+1, q[1], q[2]+1))
    if q[1]>0:
        s.append((q[0], q[1]-1, q[2]+1))
    if q[1]<w-1:
        s.append((q[0], q[1]+1, q[2]+1))
        
print(ans)

Submission status: Time Limit Exceeded

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

from collections import deque
q = deque()
for i, r in enumerate(l):
    for j, c in enumerate(r):
        if c == '#':
            l[i][j] = 0
            q.append((i, j))
d = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    y, x = q.popleft()
    for dy, dx in d:
        if (0 <= y+dy < H) and (0 <= x+dx < W) and l[y+dy][x+dx] == '.':
            l[y+dy][x+dx] = l[y][x] + 1
            q.append((y+dy, x+dx))

m = 0
for r in l:
    for c in r:
        if m < c:
            m = c
print(m)

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
a = [[j == '#' for j in input()] for _ in range(h)]

queue = deque([(i, j, 0) for i in range(h)
               for j in range(w) if a[i][j]])

ans = 0

d = ((1, 0), (0, 1), (0, -1), (-1, 0))


# def bfs(y, x, cnt):

# if (y < 0 or h <= y or x < 0 or w <= x or not a[y][x]):
#    return
#print(y, x, cnt)


while (queue):
    y, x, cnt = queue.popleft()
    # print(l)
    ans = max(ans, cnt)
    for ddx, ddy in d:
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and not a[y+ddy][x+ddx]):
            a[y+ddy][x+ddx] = True
            queue.append((y + ddy, x+ddx, cnt+1))
    # print(queue)
print(ans)

Submission status: Time Limit Exceeded

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
a = [[j == '#' for j in input()] for _ in range(h)]

queue = deque([(i, j, 0) for i in range(h)
               for j in range(w) if a[i][j]])

ans = 0

d = ((1, 0), (0, 1), (0, -1), (-1, 0))


# def bfs(y, x, cnt):

# if (y < 0 or h <= y or x < 0 or w <= x or not a[y][x]):
#    return
#print(y, x, cnt)


while (queue):
    y, x, cnt = queue.popleft()
    # print(l)
    ans = max(ans, cnt)
    for ddx, ddy in d:
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and not a[y+ddy][x+ddx]):
            a[y+ddy][x+ddx] = True
            queue.append((y + ddy, x+ddx, cnt+1))
    # print(queue)
print(ans)

Submission status: Time Limit Exceeded

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
a = [[j == '#' for j in input()] for _ in range(h)]

queue = deque([(i, j, 0) for i in range(h)
               for j in range(w) if a[i][j]])

ans = 0

dx = (1, 0, 0, -1)
dy = (0, 1, -1, 0)


# def bfs(y, x, cnt):

# if (y < 0 or h <= y or x < 0 or w <= x or not a[y][x]):
#    return
#print(y, x, cnt)


while (queue):
    y, x, cnt = queue.popleft()
    # print(l)
    ans = max(ans, cnt)
    for ddx, ddy in zip(dx, dy):
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and not a[y+ddy][x+ddx]):
            a[y+ddy][x+ddx] = True
            queue.append((y + ddy, x+ddx, cnt+1))
    # print(queue)
print(ans)

Submission status: Time Limit Exceeded

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
a = [[j == '#' for j in input()] for _ in range(h)]

queue = deque([(i, j, 0) for i in range(h)
               for j in range(w) if a[i][j]])

ans = 0

dx = (1, 0, 0, -1)
dy = (0, 1, -1, 0)


def bfs(y, x, cnt):

    # if (y < 0 or h <= y or x < 0 or w <= x or not a[y][x]):
    #    return
    #print(y, x, cnt)
    for ddx, ddy in zip(dx, dy):
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and not a[y+ddy][x+ddx]):
            a[y+ddy][x+ddx] = True
            queue.append((y + ddy, x+ddx, cnt+1))


while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])
    # print(queue)
print(ans)

Submission status: Time Limit Exceeded

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

h, w = map(int, input().split())
a = [[j == '#' for j in input()] for _ in range(h)]

queue = deque([(i, j, 0) for i in range(h)
               for j in range(w) if a[i][j]])

ans = 0

dx = (1, 0, 0, -1)
dy = (0, 1, -1, 0)


def bfs(y, x, cnt):

    if (y < 0 or h <= y or x < 0 or w <= x or not a[y][x]):
        return
    #print(y, x, cnt)
    for ddx, ddy in zip(dx, dy):
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and not a[y+ddy][x+ddx]):
            a[y+ddy][x+ddx] = True
            queue.append((y + ddy, x+ddx, cnt+1))


while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])
    # print(queue)
print(ans)

Submission status: Time Limit Exceeded

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

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

queue = collections.deque([(i, j, 0) for i in range(h)
                           for j in range(w) if a[i][j] == '#'])

ans = 0

dx = (1, 0, 0, -1)
dy = (0, 1, -1, 0)


def bfs(y, x, cnt):

    if (y < 0 or h <= y or x < 0 or w <= x or a[y][x] == '.'):
        return
    #print(y, x, cnt)
    for ddx, ddy in zip(dx, dy):
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and a[y+ddy][x+ddx] == '.'):
            a[y+ddy][x+ddx] = '#'
            queue.append((y + ddy, x+ddx, cnt+1))


while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])
    # print(queue)
print(ans)

Submission status: Time Limit Exceeded

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

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

queue = collections.deque()

ans = 0

dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]


def bfs(y, x, cnt):

    if (y < 0 or h <= y or x < 0 or w <= x or a[y][x] == '.'):
        return
    #print(y, x, cnt)
    for ddx, ddy in zip(dx, dy):
        #print(ddx, ddy)
        if (0 <= y+ddy < h and 0 <= x+ddx < w and a[y+ddy][x+ddx] == '.'):
            a[y+ddy][x+ddx] = '#'
            queue.append([y + ddy, x+ddx, cnt+1])


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

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])
    # print(queue)
print(ans)

Submission status: Time Limit Exceeded

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

# スタック最大数をセット
sys.setrecursionlimit(10**6)

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

queue = collections.deque()

ans = 0

dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x):
        return
    #print(y, x, cnt)
    a[y][x] = '#'
    for ddx, ddy in zip(dx, dy):
        if (y+ddy < 0 or h <= y+ddy or x+ddx < 0 or w <= x+ddx or a[y+ddy][x+ddx] == '.'):
            queue.append([y + ddy, x+ddx, cnt+1])


for i in range(h):
    for j in range(w):
        if (a[i][j] == '#'):
            for ddx, ddy in zip(dx, dy):
                if (i+ddy < 0 or h <= i+ddy or j+ddx < 0 or w <= j+ddx or a[i+ddy][j+ddx] == '.'):
                    queue.append([i + ddy, j+ddx, 0])

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

queue = collections.deque()

ans = 0


def bfs(y, x, cnt):
    if (y < 0 or h <= y or x < 0 or w <= x or a[y][x] == '#'):
        return
    #print(y, x, cnt)
    a[y][x] = '#'
    queue.append([y + 1, x, cnt+1])
    queue.append([y - 1, x, cnt+1])
    queue.append([y, x+1, cnt+1])
    queue.append([y, x - 1, cnt+1])


for i in range(h):
    for j in range(w):
        if (a[i][j] == '#'):
            queue.append([i+1, j, 0])
            queue.append([i-1, j, 0])
            queue.append([i, j+1, 0])
            queue.append([i, j-1, 0])

while (len(queue) > 0):
    l = queue.popleft()
    # print(l)
    ans = max(ans, l[2])
    bfs(l[0], l[1], l[2])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# AGC033A - Darker and Darker (PyPy 400ms)
def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    cur, q = 0, []
    # append default blacks to a queue
    q = [(x, y) for x in range(H) for y in range(W) if B[x][y] == 0]
    while q:  # append new blacks until all whites become black
        next_q = []
        for x, y in q:
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                    B[nx][ny] = cur + 1
                    next_q.append((nx, ny))
        q = next_q
        cur += 1
    return cur - 1


def main():
    global H, W, B
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    # default blacks: 0, whites: -1
    B = [[0 if i == "#" else -1 for i in a] for a in A]
    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# AGC033A - Darker and Darker
def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    cur, q = 0, []
    for x, b in enumerate(B):
        for y, i in enumerate(b):
            if i != cur:
                continue
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                    B[nx][ny] = cur + 1
                    q.append((nx, ny))
    while q:
        cur += 1
        next_q = []
        for x, y in q:
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                    B[nx][ny] = cur + 1
                    next_q.append((nx, ny))
        q = next_q
    return cur


def main():
    global H, W, B
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    B = [[0 if i == "#" else -1 for i in a] for a in A]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# AGC033A - Darker and Darker
def main():
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    B = [[0 if i == "#" else -1 for i in a] for a in A]
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    cur, flg = 0, 1
    while flg:
        flg = 0
        for x, b in enumerate(B):
            for y, i in enumerate(b):
                if i != cur:
                    continue
                for dx, dy in dxy:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                        B[nx][ny] = cur + 1
                        flg = 1
        cur += 1
    ans = cur - 1
    print(ans)


if __name__ == "__main__":
    main()