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 queue import Queue as queue

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    inf = h * w
    dp = [[inf for j in range(w)] for i in range(h)]

    q = queue()
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij == '#':
                q.put((i, j))
                dp[i][j] = 0

    dijs = list(zip([-1, 0, 1, 0], [0, -1, 0, 1]))
    while not q.empty():
        i, j = q.get()
        for di, dj in dijs:
            ni = i + di
            nj = j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if dp[ni][nj] <= dp[i][j] + 1: continue
            q.put((ni, nj))
            dp[ni][nj] = dp[i][j] + 1

    print(max(max(dpi) for dpi in dp))

main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
ans = 0
q = []
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.append([y, x])
black_num = len(q)
while (black_num < (h*w)):
    q_list = []
    for y, x in q:
        for i in range(4):
            new_y = y + y_list[i]
            new_x = x + x_list[i]
            if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                if map_list[new_y][new_x] == ".":
                    map_list[new_y][new_x] = "#"
                    black_num += 1
                    q_list.append([new_y, new_x])
    q = q_list.copy()
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, raw_input().split())
A = []
for i in range(H):
    A.append(raw_input())
count = 0
A2 = []
Blst = deque()
po = Blst.popleft
pu = Blst.append
s = 0
for a2 in A:
	k = []
	t = 0
	for c in a2:
		if(c =='#'):
			k.append(1)
			pu((s,t))
		else:
			k.append(0)
		t += 1
	s += 1
	A2.append(k)
count = 0
while Blst:
	hi,wi = po()
	nowt = A2[hi][wi] + 1
	if(hi != 0 and A2[hi-1][wi] == 0):
		A2[hi-1][wi] = nowt
		pu((hi-1,wi))
	if(hi != H-1 and A2[hi+1][wi] == 0):
		A2[hi+1][wi] = nowt
		pu((hi+1,wi))
	if(wi != 0 and A2[hi][wi-1] == 0):
		A2[hi][wi-1] = nowt
		pu((hi,wi-1))
	if(wi != W-1 and A2[hi][wi+1] == 0):
		A2[hi][wi+1] = nowt
		pu((hi,wi+1))
print(nowt-2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    inf = h * w
    dp = [[inf for j in range(w)] for i in range(h)]

    q = deque()
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij == '#':
                q.append((i, j))
                dp[i][j] = 0

    dijs = list(zip([-1, 0, 1, 0], [0, -1, 0, 1]))
    while q:
        i, j = q.popleft()
        for di, dj in dijs:
            ni = i + di
            nj = j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if dp[ni][nj] <= dp[i][j] + 1: continue
            q.append((ni, nj))
            dp[ni][nj] = dp[i][j] + 1

    print(max(max(dpi) for dpi in dp))

main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
ans = 0
q = []
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.append([y, x])
black_num = len(q)
map_size = h * w
while (black_num < map_size):
    q_list = []
    for y, x in q:
        for i in range(4):
            new_y = y + y_list[i]
            new_x = x + x_list[i]
            if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                if map_list[new_y][new_x] == ".":
                    map_list[new_y][new_x] = "#"
                    black_num += 1
                    q_list.append([new_y, new_x])
    q = q_list.copy()
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
dist_matrix = [[-1] * W for _ in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      dist_matrix[i][j] = 0
      queue.append((i,j))
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.popleft()
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = max_value + 1
    queue.append((i-1,j))
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = max_value + 1
    queue.append((i+1,j))
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = max_value + 1
    queue.append((i,j-1))
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = max_value + 1
    queue.append((i,j+1))
 
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, raw_input().split())
A = []
for i in range(H):
    A.append(raw_input())
count = 0
A2 = []
Blst = []
s = 0
for a2 in A:
	k = []
	t = 0
	for c in a2:
		if(c =='#'):
			k.append(1)
			Blst.append([s,t])
		else:
			k.append(0)
		t += 1
	s += 1
	A2.append(k)
count = 0
while Blst:
	Next = []
	for b in Blst:
		hi = b[0]
		wi = b[1]
		if(hi != 0 and A2[hi-1][wi] == 0):
			A2[hi-1][wi] = 1
			Next.append([hi-1,wi])
		if(hi != H-1 and A2[hi+1][wi] == 0):
			A2[hi+1][wi] = 1
			Next.append([hi+1,wi])
		if(wi != 0 and A2[hi][wi-1] == 0):
			A2[hi][wi-1] = 1
			Next.append([hi,wi-1])
		if(wi != W-1 and A2[hi][wi+1] == 0):
			A2[hi][wi+1] = 1
			Next.append([hi,wi+1])
	if(len(Next) == 0):
		break
	else:
		Blst = Next
		count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
black_num = sum([map_list[i].count("#") for i in range(h)])
ans = 0
q = Queue()
q1 = Queue()
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.put([y, x])
while (black_num < (h*w)):
    q_list = []
    for j in range(q.qsize()):
        y, x = q.get()
        if map_list[y][x] == "#":
            for i in range(4):
                new_y = y + y_list[i]
                new_x = x + x_list[i]
                if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                    if map_list[new_y][new_x] == ".":
                        map_list[new_y][new_x] = "#"
                        black_num += 1
                        q_list.append([new_y, new_x])
    q = Queue()
    for qq in q_list:
        q.put(qq)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())

M = h + w
blck = [M]*(w+2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [M]*(w+2)
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            lineN[r] = 0
    data += [lineN]
data += [blck]


for r, c, d in ((range(1, h+1), range(1,w+1), 1), (range(h, 0, -1), range(w,0,-1), -1)):
    for x in r:
        for y in c:
            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

print(max((data[x][y] for x in range(1, h+1) for y in range(1, w+1))))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())

M = h + w
blck = [M]*(w+2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [M]*(w+2)
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            lineN[r] = 0
    data += [lineN]
data += [blck]
def cp(d, s):
    d[0] = s[0]
    d[1] = s[1]
def ad(d, s):
    d[0] += s[0]
    d[1] += s[1]
def eq(d, s):
    return d[0] == s[0] and d[1] == s[1]
def eql(d, s):
    return d[0] == s[0] or d[1] == s[1]
def mn(s):
    return [-s[0], -s[1]]


cur = [0] * 2
curE = [0] * 2
addS = [0] * 2
addE = [0] * 2

for d in range(1, -2, -2):
    if d == 1:
        curS, curW, addS, addE, mov= [[1, 1], [h+1, w+1], [0, 1], [1, 0], [1, -1]]
    else:
        curS, curW, addS, addE, mov= [[h, w], [0, 0], [0, -1], [-1, 0], [-1, 1]]
    cp(curE, curS)

    for i in range(w+h-1):

        cp(cur, curS)

        while True:
            x = cur[0]
            y = cur[1]
            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

            if eq(cur, curE):
                break
            ad(cur, mov)

        ad(curS, addS)
        if eql(curS, curW):
            ad(curS, mn(addS))
            cp(addS, [addS[1], -addS[0]])
            ad(curS, addS)

        ad(curE, addE)
        if eql(curE, curW):
            ad(curE, mn(addE))
            cp(addE, [-addE[1], addE[0]])
            ad(curE, addE)

print(max((data[x][y] for x in range(1, h+1) for y in range(1, w+1))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
#dist_matrix = [[-1] * W for _ in range(H)]
dist_hash = {}
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      #dist_matrix[i][j] = 0
      dist_hash[i*W+j] = 0
      queue.append(i*W+j)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  ij = queue.popleft()
  i = ij//W
  j = ij%W
  #max_value = dist_matrix[i][j]
  max_value = dist_hash[i*W+j]
  #cnt += 1
  #if i > 0 and dist_matrix[i-1][j] == -1:
  if i > 0 and (i-1)*W+j not in dist_hash:
    #dist_matrix[i-1][j] = max_value + 1
    dist_hash[(i-1)*W+j] = max_value + 1
    queue.append((i-1)*W+j)
  #if i < H-1 and dist_matrix[i+1][j] == -1:
  if i < H-1 and (i+1)*W+j not in dist_hash:
    #dist_matrix[i+1][j] = max_value + 1
    dist_hash[(i+1)*W+j] = max_value + 1
    queue.append((i+1)*W+j)
  #if j > 0 and dist_matrix[i][j-1] == -1:
  if j > 0 and i*W+j-1 not in dist_hash:
    #dist_matrix[i][j-1] = max_value + 1
    dist_hash[i*W+j-1] = max_value + 1
    queue.append(i*W+j-1)
  #if j < W-1 and dist_matrix[i][j+1] == -1:
  if j < W-1 and i*W+j+1 not in dist_hash:
    #dist_matrix[i][j+1] = max_value + 1
    dist_hash[i*W+j+1] = max_value + 1
    queue.append(i*W+j+1)
 
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
#dist_matrix = [[-1] * W for _ in range(H)]
dist_hash = {}
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      #dist_matrix[i][j] = 0
      dist_hash[i*W+j] = 0
      queue.append([i,j])
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.popleft()
  #max_value = dist_matrix[i][j]
  max_value = dist_hash[i*W+j]
  #cnt += 1
  #if i > 0 and dist_matrix[i-1][j] == -1:
  if i > 0 and (i-1)*W+j not in dist_hash:
    #dist_matrix[i-1][j] = max_value + 1
    dist_hash[(i-1)*W+j] = max_value + 1
    queue.append([i-1,j])
  #if i < H-1 and dist_matrix[i+1][j] == -1:
  if i < H-1 and (i+1)*W+j not in dist_hash:
    #dist_matrix[i+1][j] = max_value + 1
    dist_hash[(i+1)*W+j] = max_value + 1
    queue.append([i+1,j])
  #if j > 0 and dist_matrix[i][j-1] == -1:
  if j > 0 and i*W+j-1 not in dist_hash:
    #dist_matrix[i][j-1] = max_value + 1
    dist_hash[i*W+j-1] = max_value + 1
    queue.append([i,j-1])
  #if j < W-1 and dist_matrix[i][j+1] == -1:
  if j < W-1 and i*W+j+1 not in dist_hash:
    #dist_matrix[i][j+1] = max_value + 1
    dist_hash[i*W+j+1] = max_value + 1
    queue.append([i,j+1])
 
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
func = (lambda x: 1 if x == "#" else 0)
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
func = (lambda x: 1 if x == "#" else 0)
field = [[func(i) for i in input()] for _ in range(H)]
blackQ = []

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == 1:
            blackQ.append((i, j))

ans = 0
while(True):
    bQ = []
    for _ in range(len(blackQ)):
        i, j = blackQ.pop()
        if i - 1 >= 0 and field[i-1][j] != 1:
            field[i-1][j] = 1
            bQ.append((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != 1:
            field[i+1][j] = 1
            bQ.append((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != 1:
            field[i][j-1] = 1
            bQ.append((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != 1:
            field[i][j+1] = 1
            bQ.append((i, j + 1))

    if len(bQ) == 0:
        break

    ans += 1
    blackQ = bQ.copy()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = list(input())
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(tmp)

que = []
for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que
while len(que) != H * W:
    tmp = next_que
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = input()
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(list(tmp))

que = []

for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
next_que = que.copy()
while len(que) != H * W:
    tmp = next_que.copy()
    next_que = []
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    next_que.append((x + dx, y + dy))
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
items = []
black = []
for i in range(H):
    tmp = input()
    for j in range(W):
        if tmp[j] == "#":
            black.append((i, j))
    items.append(list(tmp))

que = deque()

for b in black:
    que.append(b)

ans = 0
d4 = [(1, 0), (0, -1), (-1, 0), (0, 1)]
while len(que) != H * W:
    tmp = list(que)
    for b in list(tmp):
        x, y = b[0], b[1]
        for d in d4:
            dx = d[0]
            dy = d[1]
            if 0 <= x + dx <= H - 1 and 0 <= y + dy <= W - 1:
                tar = items[x + dx][y + dy]
                if tar == ".":
                    que.append((x + dx, y + dy))
                    items[x + dx][y + dy] = "#"
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

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

for i, wField in enumerate(field):
    for j, w in enumerate(wField):
        if w == "#":
            blackQ.put((i, j))

ans = 0
while(True):
    for _ in range(blackQ.qsize()):
        i, j = blackQ.get()
        if i - 1 >= 0 and field[i-1][j] != "#":
            field[i-1][j] = "#"
            blackQ.put((i - 1, j))
        if i + 1 <= H - 1 and field[i+1][j] != "#":
            field[i+1][j] = "#"
            blackQ.put((i + 1, j))
        if j - 1 >= 0 and field[i][j-1] != "#":
            field[i][j-1] = "#"
            blackQ.put((i, j - 1))
        if j + 1 <= W - 1 and field[i][j + 1] != "#":
            field[i][j+1] = "#"
            blackQ.put((i, j + 1))

    if blackQ.empty():
        break

    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  from array import array
  s,*c=open(0)
  h,w=map(int,s.split())
  f=array('h',[-1]*h*w)
  q=deque()
  for i,c in enumerate(''.join(t[:w]for t in c)):
    if c=='#':
      q.append(i)
      f[i]=0
  while q:
    i=q.popleft()
    v=f[i]+1
    j,k,l,m=i+w,i-w,i+1,i-1
    if h*w>j and f[j]<0:
      q.append(j)
      f[j]=v
    if k>=0 and f[k]<0:
      q.append(k)
      f[k]=v
    if w>i%w+1and f[l]<0:
      q.append(l)
      f[l]=v
    if i%w and f[m]<0:
      q.append(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  f=[-1]*h*w
  q=deque()
  for i,c in enumerate(''.join(t[:w]for t in c)):
    if c=='#':
      q.append(i)
      f[i]=0
  while q:
    i=q.popleft()
    v=f[i]+1
    j,k,l,m=i+w,i-w,i+1,i-1
    if h*w>j and f[j]<0:
      q.append(j)
      f[j]=v
    if k>=0 and f[k]<0:
      q.append(k)
      f[k]=v
    if w>i%w+1and f[l]<0:
      q.append(l)
      f[l]=v
    if i%w and f[m]<0:
      q.append(m)
      f[m]=v
  print(v-1)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[-1]*h*w
  q=deque()
  for i,d in enumerate(c):
    if d=='#':
      q.append(i)
      f[i]=0
  while q:
    y=q.popleft()
    v=f[y]
    if h*w>y+w and f[y+w]<0:
      q.append(y+w)
      f[y+w]=v+1
    if y>=w and f[y-w]<0:
      q.append(y-w)
      f[y-w]=v+1
    if w>y%w+1and f[y+1]<0:
      q.append(y+1)
      f[y+1]=v+1
    if y%w>0and f[y-1]<0:
      q.append(y-1)
      f[y-1]=v+1
  print(v)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
cs = []
q = deque()
s = set()
for h in range(H):
    cs.append(input())
    for w in range(W):
        if cs[h][w] == '#':
            s.add((h+1, w+1))
            q.append((h+1, w+1, 0))
vx = [0, 1, 0, -1]
vy = [1, 0, -1, 0]
ans = 0
# while len(s) < H * W:
# while len(q) > 0:
while q:
    y, x, n = q.popleft()
    for i in range(4):
        ny = y + vy[i]
        nx = x + vx[i]
        if ny >= 1 and ny <= H and nx >= 1 and nx <= W:
            if cs[ny-1][nx-1] == '.' and ((ny, nx) not in s):
                s.add((ny, nx))
                q.append((ny, nx, n+1))
                ans = max(ans, n+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[-1]*h*w
  q=deque()
  for i,d in enumerate(c):
    if d=='#':
      q.append(i)
      f[i]=0
  while q:
    y=q.popleft()
    v=f[y]
    y,x=divmod(y,w)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
      k=i*w+j
      if h>i>=0<=j<w and f[k]<0:
        f[k]=v+1
        q.append(k)
  print(v)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[-1]*h*w
  q=deque()
  for i in range(h*w):
    if c[i]=='#':
      q.append(i)
      f[i]=0
  while q:
    y=q.popleft()
    v=f[y]
    y,x=divmod(y,w)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
      k=i*w+j
      if h>i>=0<=j<w and'.'==c[k]*(f[k]<0):
        f[k]=v+1
        q.append(k)
  print(v)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[-1]*h*w
  q=deque()
  for i in range(h*w):
    if c[i]=='#':
      q.append((i//w,i%w))
      f[i]=0
  while q:
    y,x=q.popleft()
    v=f[y*w+x]
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
      k=i*w+j
      if h>i>=0<=j<w and'.'==c[k]*(f[k]<0):
        f[k]=v+1
        q.append((i,j))
  print(v)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())

M = h + w
data = np.ones((h+2, w+2), np.int16) * M
for ln in range(1, h+1):
    line = list(input().rstrip())
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            data[ln,r] = 0


for r, c, d in ((range(1, h+1), range(1,w+1), 1), (range(h, 0, -1), range(w,0,-1), -1)):
    for x in r:
        for y in c:
            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

print(np.max(data[1:h+1,1:w+1]))

Submission status: Time Limit Exceeded

Solution code:
def main():
  from collections import deque
  s,*c=open(0)
  h,w=map(int,s.split())
  c=''.join(t[:w]for t in c)
  f=[1]*h*w
  q=deque()
  for i in range(h*w):
    if c[i]=='#':
      q.append((i//w,i%w,0))
      f[i]=0
  while q:
    y,x,v=q.popleft()
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
      if h>i>=0<=j<w and'.'==c[i*w+j]*f[i*w+j]:
        f[i*w+j]=0
        q.append((i,j,v+1))
  print(v)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import numpy as np


A = np.array(A)
WK = np.zeros(A.shape, np.int32)
i = 0
S = H * W
while True:
    if np.min(A) == 1:
        break
    WK -= WK
    WK += A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A[:,:-1] |= WK[:,1:]
    A[:,1:] |= WK[:,:-1]
    i += 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())

M = h + w
data = np.ones((h+2, w+2), np.int16) * M
for ln in range(1, h+1):
    line = list(input().rstrip())
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            data[ln,r] = 0


for d in range(1, -2, -2):
    if d == 1:
        cur, curW, addS, addE, mov= [[1, 1], [h+1, w+1], [0, 1], [1, 0], [1, -1]]
    else:
        cur, curW, addS, addE, mov= [[h, w], [0, 0], [0, -1], [-1, 0], [-1, 1]]
    curS = np.array(cur)
    curE = curS.copy()
    addS = np.array(addS)
    addE = np.array(addE)
    mov = np.array(mov)
    for i in range(w+h-1):

        cur = curS.copy()

        while True:
            x, y = cur

            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

            if np.alltrue(cur==curE):
                break
            cur += mov

        curS += addS
        if np.max(curS == curW):
            curS -= addS
            addS = np.array([addS[1], -addS[0]])
            curS += addS


        curE += addE
        if np.max(curE== curW):
            curE -= addE
            addE = np.array([-addE[1], addE[0]])
            curE += addE

print(np.max(data[1:h+1,1:w+1]))

Submission status: Time Limit Exceeded

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

h,w=map(int,input().split())
grid=defaultdict(str)
for i in range(w+2):
    grid[(0,i)]="#"
    grid[(h+1,i)]="#"
for i in range(h):
    for k,v in enumerate(input()):
        grid[(i+1,k+1)]=v
for i in range(1,h+1):
    grid[(i,0)]="#"
    grid[(i,w+1)]="#"
#for i in range(h+2):
#    print(*[grid[(i,j)]for j in range(w+2)])

stack=deque()
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[(y,x)]=="#":
            grid[(y,x)]=str(0)
            stack.append((y,x))

for i in range(h*w):
    tmp=deque()
    while stack:
        #print(stack)
        my,mx=stack.pop()
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[(my+y,mx+x)]==".":
                grid[(my+y,mx+x)]=str(i+1)
                tmp.append((my+y,mx+x))
    stack=tmp
    if len(tmp)==0:
        print(i)
        break

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())

M = h + w
blck = [M] * (w + 2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [0] * (w+2)
    lineN[0] = lineN[-1]= M
    for r, letter in zip(range(1, w+1), line):
        if letter == '.':
            lineN[r] = M
    data.append(lineN)
data.append(blck)

data = np.array(data)

for d in range(1, -2, -2):
    if d == 1:
        cur, curW, addS, addE, mov= [[1, 1], [h+1, w+1], [0, 1], [1, 0], [1, -1]]
    else:
        cur, curW, addS, addE, mov= [[h, w], [0, 0], [0, -1], [-1, 0], [-1, 1]]
    curS = np.array(cur)
    curE = curS.copy()
    addS = np.array(addS)
    addE = np.array(addE)
    mov = np.array(mov)
    for i in range(w+h-1):

        cur = curS.copy()

        while True:
            x, y = cur

            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

            if np.alltrue(cur==curE):
                break
            cur += mov

        curS += addS
        if np.max(curS == curW):
            curS -= addS
            addS = np.array([addS[1], -addS[0]])
            curS += addS


        curE += addE
        if np.max(curE== curW):
            curE -= addE
            addE = np.array([-addE[1], addE[0]])
            curE += addE

print(np.max(data[1:h+1,1:w+1]))

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
A = [["*"]*(W+2)]
 
sum = 0
cnt = 0
 
for i in range(H):
    a = ["*"]
    a += input()
    a.append("*")
    sum += a.count("#")
    A.append(a)
A.append(["*"]*(W+2))
 
while True:
    if sum == H*W:
        break
    x = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == ".":
                for k,l in [[-1,0],[0,-1],[0,1],[1,0]]:
                    if A[i+k][j+l] == "#":
                        x.append([i,j])
                        break
 
    for i,j in x:
        A[i][j] = "#"
        sum += 1
 
    cnt += 1
 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys
import datetime
today = datetime.datetime.today

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main_ok():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [[True] * (W + 2)] + [[True] + [s == '#' for s in line] + [True] for line in A] + [[True] * (W + 2)]
    q = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == True:
                q.append((i, j))
    rec = 0
    while len(q) > 0:
        q2 = []
        ij = []
        for i0, j0 in q:
            ij.extend((
                (i0 - 1, j0),
                (i0 + 1, j0),
                (i0, j0 - 1),
                (i0, j0 + 1),
            ))
        for i, j in ij:
            if A[i][j] != True:
                A[i][j] = True
                q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

main()