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:
#  --*-coding:utf-8-*--

import numpy as np

def main():
    H, W = map(int, input().split())
    X = np.zeros((H,W), dtype="int64")
    Q = [None]*(H*W)
    lenOfQ = 0
    Q2 = [None]*(H*W)
    lenOfQ2 = 0
    
    for i in range(H):
        line = input()

        for j, c in enumerate(line):
            if c == '#':
                X[i,j] = 1
                Q[lenOfQ] = (i, j)
                lenOfQ += 1

    t = 1

    while(lenOfQ > 0):
        lenOfQ2 = 0

        for i in range(lenOfQ):
            r, c  = Q[i]

            if r > 0 and X[r-1,c] == 0:
                X[r-1,c] = t+1
                Q2[lenOfQ2] = (r-1, c)
                lenOfQ2 += 1

            if r < H-1 and X[r+1,c] == 0:
                X[r+1,c] = t+1
                Q2[lenOfQ2] = (r+1, c)
                lenOfQ2 += 1

            if c > 0 and X[r,c-1] == 0:
                X[r,c-1] = t+1
                Q2[lenOfQ2] = (r, c-1)
                lenOfQ2 += 1

            if c < W-1 and X[r,c+1] == 0:
                X[r,c+1] = t+1
                Q2[lenOfQ2] = (r, c+1)
                lenOfQ2 += 1

        if lenOfQ2 == 0:
            break

        Q, Q2 = Q2, Q
        lenOfQ = lenOfQ2

        t += 1
                
    print(t-1)


 


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

def main():
    H, W = map(int, input().split())
    X = np.zeros((H,W), dtype="int64")
    Q = [None]*(H*W)
    lenOfQ = 0
    Q2 = [None]*(H*W)
    lenOfQ2 = 0
    
    for i in range(H):
        line = input()

        for j, c in enumerate(line):
            if c == '#':
                X[i,j] = 1
                Q[lenOfQ] = (i, j)
                lenOfQ += 1

    t = 1

    while(lenOfQ > 0):
        lenOfQ2 = 0

        for r, c in Q[:lenOfQ]:
            if r > 0 and X[r-1,c] == 0:
                X[r-1,c] = t+1
                Q2[lenOfQ2] = (r-1, c)
                lenOfQ2 += 1

            if r < H-1 and X[r+1,c] == 0:
                X[r+1,c] = t+1
                Q2[lenOfQ2] = (r+1, c)
                lenOfQ2 += 1

            if c > 0 and X[r,c-1] == 0:
                X[r,c-1] = t+1
                Q2[lenOfQ2] = (r, c-1)
                lenOfQ2 += 1

            if c < W-1 and X[r,c+1] == 0:
                X[r,c+1] = t+1
                Q2[lenOfQ2] = (r, c+1)
                lenOfQ2 += 1

        if lenOfQ2 == 0:
            break

        Q, Q2 = Q2, Q
        lenOfQ = lenOfQ2

        t += 1
                
    print(t-1)


 


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import numpy as np

def main():
    H, W = map(int, input().split())
    X = np.zeros((H,W), dtype="int64")
    Q = []
    
    for i in range(H):
        line = input()

        for j, c in enumerate(line):
            if c == '#':
                X[i,j] = 1
                Q.append((i, j))

    t = 1

    while(len(Q) > 0):
        Q2 = []
        
        for r, c in Q:
            if r > 0 and X[r-1,c] == 0:
                X[r-1,c] = t+1
                Q2.append((r-1, c))

            if r < H-1 and X[r+1,c] == 0:
                X[r+1,c] = t+1
                Q2.append((r+1, c))

            if c > 0 and X[r,c-1] == 0:
                X[r,c-1] = t+1
                Q2.append((r, c-1))

            if c < W-1 and X[r,c+1] == 0:
                X[r,c+1] = t+1
                Q2.append((r, c+1))

        if len(Q2) == 0:
            break

        Q = Q2
        t += 1
                
    print(t-1)


 


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = []
C = []
for i in range(H):
	tmp = [s for s in input()]
	indexes = [k for k, x in enumerate(tmp) if x == "#"]
	A.append(tmp)
	for k in indexes:
		C.append((i,k))

c = 0
for i in range(H):
	for j in range(W):
		if A[i][j] == ".":
			tmp = H+W
			for x,y in C:
				if tmp > abs(x-i) + abs(y-j):
					tmp = abs(x-i)+abs(y-j)
					if tmp == 1:
						break
			A[i][j] = tmp
			if tmp > c:
				c = tmp
print(c)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = []
C = []
for i in range(H):
	tmp = [s for s in input()]
	indexes = [k for k, x in enumerate(tmp) if x == "#"]
	A.append(tmp)
	for k in indexes:
		C.append((i,k))

for i in range(H):
	for j in range(W):
		if A[i][j] == ".":
			tmp = H+W
			for x,y in C:
				if tmp > abs(x-i) + abs(y-j):
					tmp = abs(x-i)+abs(y-j)
			A[i][j] = tmp

tmp = 0
for i in range(H):
	for j in range(W):
		if A[i][j] != "#" and A[i][j] > tmp:
			tmp = A[i][j]
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
def check(A):
	c = 0
	for i in range(H):
		for j in range(W):
			if A[i][j] == ".":
				return 1
	return 0

H,W = map(int,input().split())
A = []
for i in range(H):
	A.append([s for s in input()])

c = 0
while check(A) != 0:
	for i in range(H):
		for j in range(W):
			if A[i][j] != "." and A[i][j] != c:
				if i != 0:
					if A[i-1][j] == ".":
						A[i-1][j] = c
				if i != H-1:
					if A[i+1][j] == ".":
						A[i+1][j] = c
				if j != 0:
					if A[i][j-1] == ".":
						A[i][j-1] = c
				if j != W-1:
					if A[i][j+1] == ".":
						A[i][j+1] = c
	c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
def check(A):
	c = 0
	for i in range(H):
		for j in range(W):
			if A[i][j] == ".":
				return 1
	return 0

def change(A):
	for i in range(H):
		for j in range(W):
			if A[i][j] == "?":
				A[i][j] = "#"
	return A

H,W = map(int,input().split())
A = []
for i in range(H):
	A.append([s for s in input()])

c = 0
while check(A) != 0:
	for i in range(H):
		for j in range(W):
			if A[i][j] == "#":
				if i != 0:
					if A[i-1][j] != "#":
						A[i-1][j] = "?"
				if i != H-1:
					if A[i+1][j] != "#":
						A[i+1][j] = "?"
				if j != 0:
					if A[i][j-1] != "#":
						A[i][j-1] = "?"
				if j != W-1:
					if A[i][j+1] != "#":
						A[i][j+1] = "?"
	A = change(A)
	c += 1
print(c)

Submission status: Time Limit Exceeded

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


def main():
    H, W = map(int, input().split())
    X = [[None]*W for _ in range(H)]
    Q = []
    
    for i in range(H):
        line = input()
        Xi = X[i]

        for j, c in enumerate(line):
            if c == '#':
                Xi[j] = 0
                Q.append((i, j))

    t = 0

    while(len(Q) > 0):
        Q2 = []
        
        for r, c in Q:
            if r > 0 and X[r-1][c] == None:
                X[r-1][c] = t+1
                Q2.append((r-1, c))

            if r < H-1 and X[r+1][c] == None:
                X[r+1][c] = t+1
                Q2.append((r+1, c))

            if c > 0 and X[r][c-1] == None:
                X[r][c-1] = t+1
                Q2.append((r, c-1))

            if c < W-1 and X[r][c+1] == None:
                X[r][c+1] = t+1
                Q2.append((r, c+1))

        if len(Q2) == 0:
            break

        Q = Q2
        t += 1
                
    print(t)


 


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def f(q):
    global H,W,A
    B = []
    for Q in q:
        h,w = Q[0],Q[1]
        if h+1!=H and A[h+1][w]==".":
            B.append([h+1,w])
            A[h+1][w]="#"
        if h-1!=-1 and A[h-1][w]==".":
            B.append([h-1,w])
            A[h-1][w]="#"
        if w+1!=W and A[h][w+1]==".":
            B.append([h,w+1])
            A[h][w+1]="#"
        if w-1!=-1 and A[h][w-1]==".":
            B.append([h,w-1])
            A[h][w-1]="#"
    return B
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
ans = 0
q = []
for h in range(H):
    for w in range(W):
        if A[h][w]=="#": q.append([h,w])
while q:
    ans+=1
    q = f(q)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
H, W = map(int, input().split())
is_visited = [[False for w in range(W)] for h in range(H)]
q = Queue()
for h in range(H):
    Ah = list(input())
    for w in range(W):
        if Ah[w] == '#':
            q.put((h, w, 0))
            is_visited[h][w] = True
ans = 0
lrud = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1]
]
while not q.empty():
    x, y, c = q.get()
    for dx, dy in lrud:
        nx = min(max(0, x+dx), H-1)
        ny = min(max(0, y+dy), W-1)
        if not is_visited[nx][ny]:
            q.put((nx, ny, c+1))
            is_visited[nx][ny] = True
    ans = c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
H, W = map(int, input().split())
A = [['.' for w in range(W)] for h in range(H)]
is_visited = [[False for w in range(W)] for h in range(H)]
q = Queue()
for h in range(H):
    A[h] = list(input())
    for w in range(W):
        if A[h][w] == '#':
            q.put((h, w, 0))
            is_visited[h][w] = True
ans = 0
lrud = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1]
]
while not q.empty():
    x, y, c = q.get()
    for dx, dy in lrud:
        nx = min(max(0, x+dx), H-1)
        ny = min(max(0, y+dy), W-1)
        if not is_visited[nx][ny]:
            q.put((nx, ny, c+1))
            is_visited[nx][ny] = True
    ans = c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split()) # 横に2個
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W+1)] for _ in range(H+1)]
qs = []
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            qs.append([h, w])
            checked[h][w] = True
for h in range(H+1):
    checked[h][W] = True
for w in range(W+1):
    checked[H][w] = True

c = 0
while qs:
    qqs = []
    for h,w in qs:
        checked[h][w] = True
        if 0 < h and not checked[h-1][w]:
            qqs.append([h-1, w])
        if h < H-1 and not checked[h+1][w]:
            qqs.append([h+1, w])
        if 0 < w and not checked[h][w-1]:
            qqs.append([h, w-1])
        if w < W-1 and not checked[h][w+1]:
            qqs.append([h, w+1])
    if not qqs:
        break
    c += 1
    qs = qqs

print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split()) # 横に2個
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W+1)] for _ in range(H+1)]
qs = []
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            qs.append([h, w])
            checked[h][w] = True
for h in range(H+1):
    checked[h][W] = True
for w in range(W+1):
    checked[H][w] = True

c = -1
while qs:
    qqs = []
    for h,w in qs:
        checked[h][w] = True
        next = [[h+1, w], [h-1, w], [h, w+1], [h, w-1]]
        for hn, wn in next:
            if not checked[hn][wn]:
                qqs.append([hn, wn])
    c += 1
    qs = qqs

print(c)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split()) # 横に2個
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W)] for _ in range(H)]
qs = []
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            qs.append([h, w])
            checked[h][w] = True

c = -1
while qs:
    qqs = []
    for h,w in qs:
        checked[h][w] = True
        next = [[h+1, w], [h-1, w], [h, w+1], [h, w-1]]
        for hn, wn in next:
            if 0<=hn<=H-1 and 0<=wn<=W-1:
                if not checked[hn][wn]:
                    qqs.append([hn, wn])
    c += 1
    qs = qqs

print(c)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
board = []
cnt = 0
for _ in range(h):
  row = [0 if c=='.' else 1 for c in input()]
  cnt += sum(row)
  board.append(row)

iter = 0
while cnt < h*w:
  iter += 1
  for i in range(h):
    for j in range(w):
      if board[i][j] != iter:
        continue
      
      if i != 0:
        if board[i-1][j] == 0:
          cnt += 1
          board[i-1][j] = iter + 1
      
      if i != h-1:
        if board[i+1][j] == 0:
          cnt += 1
          board[i+1][j] = iter + 1
      
      if j != 0:
        if board[i][j-1] == 0:
          cnt += 1
          board[i][j-1] = iter + 1
      
      if j != w-1:
        if board[i][j+1] == 0:
          cnt += 1
          board[i][j+1] = iter + 1
            
print(iter)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
board = []
cnt = 0
for _ in range(h):
  s = input()
  row = []
  for c in s:
    if c == '.':
      row.append(0)
    else:
      row.append(1)
      cnt += 1
  board.append(row)

iter = 0
while cnt < h*w:
  iter += 1
  for i in range(h):
    for j in range(w):
      if board[i][j] != iter:
        continue
      
      if i != 0:
        if board[i-1][j] == 0:
          cnt += 1
          board[i-1][j] = iter + 1
      
      if i != h-1:
        if board[i+1][j] == 0:
          cnt += 1
          board[i+1][j] = iter + 1
      
      if j != 0:
        if board[i][j-1] == 0:
          cnt += 1
          board[i][j-1] = iter + 1
      
      if j != w-1:
        if board[i][j+1] == 0:
          cnt += 1
          board[i][j+1] = iter + 1
            
print(iter)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import queue

H, W = [int(x) for x in stdin.readline().rstrip().split()]
B = [list(stdin.readline().rstrip()) for _ in range(H)]

q = queue.Queue()

for k in range(H):
    for l in range(W):
        if B[k][l] == '#':
            q.put((k, l, 0))

while not q.empty():
    h, w, t = q.get()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            q.put((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            q.put((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            q.put((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            q.put((h, w + 1, t + 1))
    if q.empty():
        print(t)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import queue

H, W = [int(x) for x in stdin.readline().rstrip().split()]
A = [stdin.readline().rstrip() for _ in range(H)]
B = [[A[y][x] for x in range(W)] for y in range(H)]
q = queue.Queue()

for k in range(H):
    for l in range(W):
        if A[k][l] == '#':
            q.put((k, l, 0))

while not q.empty():
    h, w, t = q.get()
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            q.put((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            q.put((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            q.put((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            q.put((h, w + 1, t + 1))
    if q.empty():
        print(t)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

H, W = [int(x) for x in stdin.readline().rstrip().split()]
A = [stdin.readline().rstrip() for _ in range(H)]
B = [[A[y][x] for x in range(W)] for y in range(H)]
queue = []

for k in range(H):
    for l in range(W):
        if A[k][l] == '#':
            queue.append((k, l, 0))

while len(queue) > 0:
    h, w, t = queue.pop(0)
    if h > 0:
        if B[h - 1][w] == '.':
            B[h - 1][w] = '#'
            queue.append((h - 1, w, t + 1))
    if h < H - 1:
        if B[h + 1][w] == '.':
            B[h + 1][w] = '#'
            queue.append((h + 1, w, t + 1))
    if w > 0:
        if B[h][w - 1] == '.':
            B[h][w - 1] = '#'
            queue.append((h, w - 1, t + 1))
    if w < W - 1:
        if B[h][w + 1] == '.':
            B[h][w + 1] = '#'
            queue.append((h, w + 1, t + 1))
    if len(queue) == 0:
        print(t)

Submission status: Time Limit Exceeded

Solution code:

import queue as que



def main():
    h, w = map(int, input().split())

    ahw = [input() for _ in range(h)]

    board = [[0]*w for _ in range(h)]

    q = que.Queue(h*w)
    q.put((-1,-1))
#    q = [(-1,-1)]
    
    for hi in range(h):
        for wi in range(w):
            if ahw[hi][wi] == '#':

                board[hi][wi] = 1
                
                q.put( (hi,wi) )

#    print(q)
#    print(board)
    if q.full():
        print(0)
        return 
    

    def exec(h_,w_):
        if board[h_][w_] == 0:
            q.put((h_,w_))
            board[h_][w_] = 1
   
           
    ans = 0
    while not q.empty():
        t = q.get()
#        print(t)
        th = t[0]; tw = t[1]

        if th == tw and tw == -1:
            if q.empty():
                break

            q.put((-1,-1))
            ans += 1
            continue

        if 0<th:
            exec(th-1, tw)
        if th+1 <h:
            exec(th+1, tw)
        if 0<tw:
            exec(th, tw-1)
        if tw +1 <w:
            exec(th, tw+1)

    print(ans-1)

main()

Submission status: Time Limit Exceeded

Solution code:

import queue as que



def main():
    h, w = map(int, input().split())

    ahw = [input() for _ in range(h)]

    board = [[0]*w for _ in range(h)]


    q = [(-1,-1)]
    
    for hi in range(h):
        for wi in range(w):
            if ahw[hi][wi] == '#':

                board[hi][wi] = 1
                
                q.append( (hi,wi) )

#    print(q)
#    print(board)
    if len(q) == w*h:
        print(0)
        return 
    

    def exec(h_,w_):
        if board[h_][w_] == 0:
            q.append((h_,w_))
            board[h_][w_] = 1
   
           
    ans = 0
    while q:
        t = q.pop(0)
#        print(t)
        th = t[0]; tw = t[1]
        if th == tw and tw==-1:
            if not q:
                continue

            q.append((-1,-1))
            ans += 1
            continue

        if 0<th:
            exec(th-1, tw)
        if th+1 <h:
            exec(th+1, tw)
        if 0<tw:
            exec(th, tw-1)
        if tw +1 <w:
            exec(th, tw+1)

    print(ans-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import queue

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = queue.Queue()
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.put((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while not q.empty():
    pos = q.get()
    ans = max(ans, D[pos[0]][pos[1]])
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = pos[0] + y
        nx = pos[1] + x
        if 0 <= nx and nx < W and 0 <= ny and ny < H:
            if D[ny][nx] < 0:
                D[ny][nx] = D[pos[0]][pos[1]] + 1
                q.put((ny, nx))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
block = []
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#": block.append((i, j))
    A.append(S)

max_op_count = 0
for i in range(H):
    for j in range(W):
        pos_str = A[i][j]
        if pos_str == ".":
            max_op_count = max(max_op_count, min([abs(i - x) + abs(j - y) for (x, y) in block]))

print(max_op_count)

Submission status: Time Limit Exceeded

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

def bfs():
    q = blacks
    c = 0
    while q != []:
        x,y,d = q.pop(0)
        c = max(c, d)
        for dx,dy in [(0,1), (1,0), (-1,0), (0,-1)]:
            nx = x+dx
            ny = y+dy
            if 0 <= nx < W and 0 <= ny < H:
                if brd[ny][nx] == ".":
                    brd[ny][nx] = "#"
                    q.append((nx, ny, d+1))
    return c
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int,input().split())
brd = []
blacks = []
for i in range(H):
    brd.append(list(input()))
    for j in range(W):
        if brd[i][j] == "#":
            blacks.append((j, i, 0))

def bfs():
    q = blacks
    c = 0
    while q != []:
        x,y,d = q.pop(0)
        c = max(c, d)
        for dx,dy in [(0,1), (1,0), (-1,0), (0,-1)]:
            nx = x+dx
            ny = y+dy
            if 0 <= nx < W and 0 <= ny < H:
                if brd[ny][nx] == ".":
                    brd[ny][nx] = "#"
                    q.append((nx, ny, d+1))
    return c
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
board = []
cnt = 0
for _ in range(h):
  s = input()
  row = []
  for c in s:
    if c == '.':
      row.append(0)
    else:
      row.append(1)
      cnt += 1
  board.append(row)

iter = 0
while cnt < h*w:
  iter += 1
  for i in range(h):
    for j in range(w):
      if board[i][j] != iter:
        continue
      
      if i != 0:
        if board[i-1][j] == 0:
          cnt += 1
        board[i-1][j] = iter + 1
      
      if i != h-1:
        if board[i+1][j] == 0:
          cnt += 1
        board[i+1][j] = iter + 1
      
      if j != 0:
        if board[i][j-1] == 0:
          cnt += 1
        board[i][j-1] = iter + 1
      
      if j != w-1:
        if board[i][j+1] == 0:
          cnt += 1
        board[i][j+1] = iter + 1
            
print(iter)

Submission status: Time Limit Exceeded

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

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

    white = [[False] * w for i in range(h)]

    q = deque()
    for y in range(h):
        for x in range(w):
            if board[y][x] == ".":
                white[y][x] = True
            else:
                q.append((x, y, 0))

    step = 0
    len_ = len(q)
    while len_ > 0:
        x, y, step = q.popleft()
        len_ -= 1
        for n_x, n_y in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0 <= n_x and n_x < w and 0 <= n_y and n_y < h:
                if white[n_y][n_x]:
                    q.append((n_x, n_y, step+1))
                    len_ += 1
                    white[n_y][n_x] = False

    print(step)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
board = [list(input().strip()) for i in range(h)]

white = [[False] * w for i in range(h)]

q = deque()
for y in range(h):
    for x in range(w):
        if board[y][x] == ".":
            white[y][x] = True
        else:
            q.append((x, y, 0))

step = 0
while len(q) > 0:
    x, y, step = q.popleft()
    for n_x, n_y in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
        if 0 <= n_x and n_x < w and 0 <= n_y and n_y < h:
            if white[n_y][n_x]:
                q.append((n_x, n_y, step+1))
                white[n_y][n_x] = False

print(step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
board = [list(input().strip()) for i in range(h)]

white = [[False] * w for i in range(h)]

q = deque()
for y in range(h):
    for x in range(w):
        if board[y][x] == ".":
            white[y][x] = True
        else:
            q.append((x, y, 0))

ans = 0
while len(q) > 0:
    x, y, step = q.popleft()
    ans = max(ans, step)
    for n_x, n_y in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
        if 0 <= n_x and n_x < w and 0 <= n_y and n_y < h:
            if white[n_y][n_x]:
                q.append((n_x, n_y, step+1))
                white[n_y][n_x] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import copy

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

A = []

for i in range(H):

    a = input()
    la = list(a)
    A.append(la)

Q = []

for i in range(H):
    for j in range(W):

        if A[i][j] == "#":
            A[i][j] = 0
            Q.append([i,j])

ans = 0

while len(Q) > 0:

    now = Q.pop(0)

    if now[0]-1 >= 0 and A[now[0]-1][now[1]] == ".":

        A[now[0]-1][now[1]] = A[now[0]][now[1]] + 1
        Q.append ([ now[0]-1 , now[1] ])

    if now[0]+1 < H and A[now[0]+1][now[1]] == ".":

        A[now[0]+1][now[1]] = A[now[0]][now[1]] + 1
        Q.append ([ now[0]+1 , now[1] ])

    if now[1]-1 >= 0 and A[now[0]][now[1]-1] == ".":

        A[now[0]][now[1]-1] = A[now[0]][now[1]] + 1
        Q.append ([ now[0] , now[1]-1 ])

    if now[1]+1 < W and A[now[0]][now[1]+1] == ".":

        A[now[0]][now[1]+1] = A[now[0]][now[1]] + 1
        Q.append ([ now[0] , now[1]+1 ])

print(A[now[0]][now[1]])

Submission status: Time Limit Exceeded

Solution code:
import copy

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

A = []

for i in range(H):

    a = input()
    la = list(a)
    A.append(la)

flag = True
cnt = 1

#print (A)

while flag:


    flag = False

    OA = copy.deepcopy(A)

    for i in range(H):

        for j in range(W):


            if OA[i][j] != ".":

                if i-1 >= 0:
                    
                    if OA[i-1][j] == ".":
                        A[i-1][j] = cnt
                        flag = True

                if i+1 < H:
                    
                    if OA[i+1][j] == ".":
                        A[i+1][j] = cnt
                        flag = True

                if j-1 >= 0:
                    
                    if OA[i][j-1] == ".":
                        A[i][j-1] = cnt
                        flag = True

                if j+1 < W:

                    #print (j+1)
                    
                    if OA[i][j+1] == ".":
                        A[i][j+1] = cnt
                        flag = True

    if flag:
        cnt += 1
    #print (OA)
    #print (A)
    #print (cnt)


print (cnt-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[]
ans=0
s=set()
from collections import deque
q=deque([])
l=[[10**10 for i in range(w)]for j in range(h)]
for i in range(h):
    p=input()
    a.append(p)
    for j in range(w):
        if p[j]=="#":
            q.append((i,j))
            l[i][j]=0
        else:
            s.add((i,j))

while s:
    i,j=q.popleft()
    if (i-1,j) in s:
        s.remove((i-1,j))
        q.append((i-1,j))
        l[i-1][j]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    if (i+1,j) in s:
        s.remove((i+1,j))
        q.append((i+1,j))
        l[i+1][j]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    if (i,j-1) in s:
        s.remove((i,j-1))
        q.append((i,j-1))
        l[i][j-1]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    if (i,j+1) in s:
        s.remove((i,j+1))
        q.append((i,j+1))
        l[i][j+1]=l[i][j]+1
        ans=max(ans,l[i][j]+1)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[]
s=set()
from collections import deque
q=deque([])
l=[[10**10 for i in range(w)]for j in range(h)]
for i in range(h):
    p=input()
    a.append(p)
    for j in range(w):
        if p[j]=="#":
            q.append((i,j))
            l[i][j]=0
        else:
            s.add((i,j))

while s:
    i,j=q.popleft()
    if (i-1,j) in s:
        s.remove((i-1,j))
        q.append((i-1,j))
        l[i-1][j]=min(l[i-1][j],l[i][j]+1)
    if (i+1,j) in s:
        s.remove((i+1,j))
        q.append((i+1,j))
        l[i+1][j]=min(l[i+1][j],l[i][j]+1)
    if (i,j-1) in s:
        s.remove((i,j-1))
        q.append((i,j-1))
        l[i][j-1]=min(l[i][j-1],l[i][j]+1)
    if (i,j+1) in s:
        s.remove((i,j+1))
        q.append((i,j+1))
        l[i][j+1]=min(l[i][j+1],l[i][j]+1)
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = ['#' * (w+2)] + ['#' + input() + '#' for i in range(h)] + ['#' * (w+2)]
for i in range(h+2):
    a[i] = list(a[i])

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

ans = 0
while x:
    y = []
    for i, j in x:
        for di, dj in d:
            if a[i+di][j+dj] == '.':
                a[i+di][j+dj] = '#'
                y.append((i+di, j+dj))
    x = y.copy()
    ans += 1
    # for i in range(h+2):
    #     print("".join(a[i]))
    # print()

ans -= 1
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    h,w = map(int,input().split())
    q = []
    A = ["" for i in range(h)]
    for i in range(h):
        b = input()
        A[i] = b
    #    print(b)
        for j in range(w):
            if b[j]=="#": q.append([i,j,0])
    #print(A)
    while q:
        a,b,c = q.pop(0)
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=b+y<h and 0<=a+x<w and A[b+y][a+x] == ".":
                #print(b+y,a+x)
                q.append([b+y,a+x,c+1])
                l = list(A[b+y])
                l[a+x] = "#"
                A[b+y] = "".join(l)
        if not q:
            print(c)
            break
    #print(A)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    h,w = map(int,input().split())
    q = queue.Queue()
    A = ["" for i in range(h)]
    for i in range(h):
        b = input()
        A[i] = b
    #    print(b)
        for j in range(w):
            if b[j]=="#": q.put([i,j,0])
    #print(A)
    while not q.empty():
        a,b,c = q.get()
        for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=b+y<h and 0<=a+x<w and A[b+y][a+x] == ".":
                #print(b+y,a+x)
                q.put([b+y,a+x,c+1])
                l = list(A[b+y])
                l[a+x] = "#"
                A[b+y] = "".join(l)
        if q.empty():
            print(c)
            break
    #print(A)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
q = queue.Queue()
A = ["" for i in range(h)]
for i in range(h):
    b = input()
    A[i] = b
#    print(b)
    for j in range(w):
        if b[j]=="#": q.put([i,j,0])
#print(A)
while not q.empty():
    a,b,c = q.get()
    for x,y in [(1,0),(0,1),(-1,0),(0,-1)]:
        if 0<=b+y<h and 0<=a+x<w and A[b+y][a+x] == ".":
            #print(b+y,a+x)
            q.put([b+y,a+x,c+1])
            l = list(A[b+y])
            l[a+x] = "#"
            A[b+y] = "".join(l)
    if q.empty():
        print(c)
        break
#print(A)