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:
def add_black(p):
  x, y = p
  ret = set()
  if (x + 1, y) in w:
    ret.add((x + 1, y))
    w.remove((x + 1, y))
  if (x - 1, y) in w:
    ret.add((x - 1, y))
    w.remove((x - 1, y))
  if (x, y + 1) in w:
    ret.add((x, y + 1))
    w.remove((x, y + 1))
  if (x, y - 1) in w:
    ret.add((x, y - 1))
    w.remove((x, y - 1))
  return ret


height, width = map(int, input().split())
w = set()
queue = []
for i in range(height):
  line = input()
  for j in range(width):
    if line[j] == "#":
      queue += [(i, j)]
    else:
      w.add((i, j))

count = 0
while len(w) != 0:
  # print(queue)
  # print(w)
  next_queue = []    
  for q in queue:
    next_queue += add_black(q)
  queue = next_queue
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h, w_list in enumerate(m_list[1:-1]):
        for w, a in enumerate(w_list[1:-1]):
            if a:
                q_list.append((h+1, w+1))
    bfs(q_list)

Submission status: Time Limit Exceeded

Solution code:
def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append([h, w+1])
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append([h+1, w])
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append([h, w-1])
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append([h-1, w])
        q_list = new_q_list
    return cnt


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h, w_list in enumerate(m_list[1:-1]):
        for w, a in enumerate(w_list[1:-1]):
            if a:
                q_list.append([h+1, w+1])
    ans = bfs(q_list)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h_len, w_len = map(int, input().split())
m_list = [[True for _ in range(w_len+2)]]
for _ in range(h_len):
    m_list.append([True] + [s=='#' for s in input()] + [True])
m_list.append([True for _ in range(w_len+2)])
q_list = []
for h, w_list in enumerate(m_list[1:-1]):
    for w, a in enumerate(w_list[1:-1]):
        if a:
            q_list.append([h+1, w+1])
dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
cnt = -1
while q_list:
    cnt += 1
    new_q_list = []
    for h, w in q_list:
        for dx, dy in zip(dx_list, dy_list):
            x, y = w+dx, h+dy
            if not m_list[y][x]:
                m_list[y][x] = True
                new_q_list.append([y, x])
    q_list = new_q_list
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len, q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            for dx, dy in zip(dx_list, dy_list):
                x, y = w+dx, h+dy
                if not m_list[y][x]:
                    m_list[y][x] = True
                    new_q_list.append([y, x])
        q_list = new_q_list
    return cnt


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = []
    tmp_list = [True for _ in range(w_len+2)]
    m_list.append(tmp_list)
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append(tmp_list)
    q_list = []
    for h, w_list in enumerate(m_list[1:-1]):
        for w, a in enumerate(w_list[1:-1]):
            if a:
                q_list.append([h+1, w+1])
    ans = bfs(h_len, w_len, q_list)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len, q_list):
    cnt = 0
    while True:
        new_q_list = []
        for q in q_list:
            h, w = q[0], q[1]
            for dx, dy in zip(dx_list, dy_list):
                x, y = w+dx, h+dy
                if m_list[y][x] == 0:
                    m_list[y][x] = 1
                    new_q_list.append([y, x])
        if len(new_q_list) == 0:
            break
        else:
            cnt += 1
            q_list = new_q_list
    return cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    m_list = [[1 for _ in range(w_len+2)]]
    for _ in range(h_len):
        s = input()[:-1]
        m_list.append([1] + [1 if i == '#' else 0 for i in s] + [1])
    m_list.append([1 for _ in range(w_len+2)])
    q_list = []
    for h, w_list in enumerate(m_list[1:-1]):
        for w, a in enumerate(w_list[1:-1]):
            if a == 1:
                q_list.append([h+1, w+1])
    ans = bfs(h_len, w_len, q_list)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len, q_list):
    cnt = 0
    while len(q_list)>0:
        new_q_list = []
        for q in q_list:
            h, w = q[0], q[1]
            for dx, dy in zip(dx_list, dy_list):
                x = w + dx
                y = h + dy
                if 0 <= x < w_len and 0 <= y < h_len and m_list[y][x] == 0:
                    m_list[y][x] = 1
                    new_q_list.append([y, x])
        if len(new_q_list) == 0:
            break
        else:
            cnt += 1
            q_list = new_q_list
    return cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    m_list = []
    for _ in range(h_len):
        s = input()[:-1]
        m_list.append([1 if i == '#' else 0 for i in s])
    q_list = []
    for h, w_list in enumerate(m_list):
        for w, check in enumerate(w_list):
    	    if check == 1:
    		    q_list.append([h, w])
    ans = bfs(h_len, w_len, q_list)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len):
    max_cnt = 0
    for _ in range(h_len*w_len+1):
        u_list = bfs_q.popleft()
        h, w, cnt = u_list[0], u_list[1], u_list[2]
        max_cnt = max(max_cnt, cnt)
        for dx, dy in zip(dx_list, dy_list):
            x = w + dx
            y = h + dy
            if 0 <= x < w_len and 0 <= y < h_len and m[y][x] == 0:
                m[y][x] = 1
                bfs_q.append([y, x, cnt+1])
        if len(bfs_q) == 0:
            break        
    return max_cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    a_list = []
    for _ in range(h_len):
        s = input()[:-1]
        a_list.append(s)
    m = []
    bfs_q = deque([])
    for h, w_list in enumerate(a_list):
        tmp_list = []
        for w, a in enumerate(w_list):
            if a == '#':
                tmp_list.append(1)
                bfs_q.append([h, w, 0])
            else:
                tmp_list.append(0)
        m.append(tmp_list)
    ans = bfs(h_len, w_len)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


dx_list = [1, 0, -1, 0]
dy_list = [0, -1, 0, 1]
def bfs(h_len, w_len):
    max_cnt = 0
    while len(bfs_q)>0:
        u_list = bfs_q.popleft()
        h, w, cnt = u_list[0], u_list[1], u_list[2]
        max_cnt = max(max_cnt, cnt)
        for dx, dy in zip(dx_list, dy_list):
            x = w + dx
            y = h + dy
            if 0 <= x < w_len and 0 <= y < h_len and m[y][x] == 0:
                m[y][x] = 1
                bfs_q.append([y, x, cnt+1])
    return max_cnt


if __name__ == "__main__":
    input = sys.stdin.readline
    h_len, w_len = map(int, input().split())
    m = [[0]*w_len for _ in range(h_len)]
    a_list = []
    for _ in range(h_len):
        s = input()[:-1]
        a_list.append(s)
    bfs_q = deque([])
    for h, w_list in enumerate(a_list):
        for w, a in enumerate(w_list):
            if a == '#':
                m[h][w] = 1
                bfs_q.append([h, w, 0])
    ans = bfs(h_len, w_len)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def add_black(p):
  x, y = p
  ret = []
  if (x + 1, y) in w:
    ret += [(x + 1, y)]
    del w[(x + 1, y)]
  if (x - 1, y) in w:
    ret += [(x - 1, y)]
    del w[(x - 1, y)]
  if (x, y + 1) in w:
    ret += [(x, y + 1)]
    del w[(x, y + 1)]
  if (x, y - 1) in w:
    ret +=[(x, y - 1)]
    del w[(x, y -1)]
  return ret


height, width = map(int, input().split())
w = {}
queue = []
for i in range(height):
  line = input()
  for j in range(width):
    if line[j] == "#":
      queue += [(i, j)]
    else:
      w[(i, j)] = 1

count = 0
while len(w) != 0:
  # print(queue)
  # print(w)
  next_queue = []    
  for q in queue:
    next_queue += add_black(q)
  queue = next_queue
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def add_black(p):
  x, y = p
  ret = []
  if (x + 1, y) in w:
    ret.append((x + 1, y))
    del w[(x + 1, y)]
  if (x - 1, y) in w:
    ret.append((x - 1, y))
    del w[(x - 1, y)]
  if (x, y + 1) in w:
    ret.append((x, y + 1))
    del w[(x, y + 1)]
  if (x, y - 1) in w:
    ret.append((x, y - 1))
    del w[(x, y -1)]
  return ret


height, width = map(int, input().split())
b = {}
w = {}
queue = []
for i in range(height):
  line = input()
  for j in range(width):
    if line[j] == "#":
      b[(i, j)] = 1
      queue.append((i, j))
    else:
      w[(i, j)] = 1

count = 0
while len(w) != 0:
  # print(queue)
  # print(w)
  next_queue = []    
  for q in queue:
    next_queue += add_black(q)
  queue = next_queue.copy()
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
import numpy as np

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

# 初期値
queue = deque([
    [i, j] for i, j in itertools.product(
        range(h), range(w)) if a[i][j]=='#'])

# 黒塗り済みセル
blacked = [[
    int([i, j] in queue)-1 for j in range(w)] 
    for i in range(h) ]

while queue:
    y, x = queue.popleft()
    
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+j, x+k
        
        if new_y < 0 or new_x < 0 or new_y > h-1 or new_x > w-1:
            continue
        
        if a[new_y][new_x] == '.' and \
            blacked[new_y][new_x] == -1:
            
            blacked[new_y][new_x] = blacked[y][x] + 1
            queue.append([new_y, new_x])
            
print(np.max(blacked))

Submission status: Time Limit Exceeded

Solution code:
import queue

class Solver(object):
    def handle(self, i, j, count):
        if i < 0 or j < 0 or i >= self.h or j >= self.w:
            return

        if self.a[i][j] == '#':
            return

        self.a[i][j] = '#'
        if count > self.max:
            self.max = count
      
        self.q.put((i, j, count + 1))

    def run(self):
        self.max = 0
        self.h, self.w = [int(x) for x in input().split(' ')]
        self.a = []
        for i in range(self.h):
            self.a.append(list(input().rstrip()))

        self.q = queue.Queue()
        for i in range(self.h):
            for j in range(self.w):
                if self.a[i][j] == '#':
                    self.q.put((i, j, 1))

        while not self.q.empty():
            i, j, c = self.q.get()
            self.handle(i - 1, j, c)
            self.handle(i + 1, j, c)
            self.handle(i, j - 1, c)
            self.handle(i, j + 1, c)
        
        print(self.max)

Solver().run()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=(int(i) for i in input().split())
#print(h,w)

a=[[i for i in input()] for j in range(h)]
#print(a)

start=deque([])
goal=deque([])
for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            goal.append((i,j))
        else:
            start.append((i,j))
#print(goal)
#print(start)

cnt=0
for i in range(len(goal)):
    cnt1=2010    
    for j in range(len(start)):
        length=abs(goal[i][0]-start[j][0])+abs(goal[i][1]-start[j][1])
        if length < cnt1:
            cnt1= length
    if cnt < cnt1:
        cnt = cnt1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='#':
      q.append((i,j,0))
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append((y+dy[i],x+dx[i],cnt+1))
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break

Submission status: Time Limit Exceeded

Solution code:
def cnt(h,w):
  q=[]
  arr=[[True]*(w+2)]
  arr.extend([[True]+[s!='.' for s in input()]+[True] for _ in range(h)])
  arr.append([True]*(w+2))
  for i in range(1,h+1):
    for j in range(1,w+1):
      if arr[i][j]:
        q.append([i,j])
  ans=0
  while 1:
    nq=[]
    for y,x in q:
      if not arr[y-1][x]:
        nq.append([y-1,x])
        arr[y-1][x]=True
      if not arr[y][x-1]:
        nq.append([y,x-1])
        arr[y][x-1]=True
      if not arr[y+1][x]:
        nq.append([y+1,x])
        arr[y+1][x]=True
      if not arr[y][x+1]:
        nq.append([y,x+1])
        arr[y][x+1]=True
    if len(nq)==0:
      break
    else:
      q=nq
      ans+=1
  return ans
    
h,w=map(int,input().split())
print(cnt(h,w))

Submission status: Time Limit Exceeded

Solution code:
q=[]
h,w=map(int,input().split())
arr=[[True]*(w+2)]
arr.extend([[True]+[s!='.' for s in input()]+[True] for _ in range(h)])
arr.append([True]*(w+2))
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j])
ans=0
while 1:
  nq=[]
  for y,x in q:
    if not arr[y-1][x]:
      nq.append([y-1,x])
      arr[y-1][x]=True
    if not arr[y][x-1]:
      nq.append([y,x-1])
      arr[y][x-1]=True
    if not arr[y+1][x]:
      nq.append([y+1,x])
      arr[y+1][x]=True
    if not arr[y][x+1]:
      nq.append([y,x+1])
      arr[y][x+1]=True
  if len(nq)==0:
    break
  else:
    q=nq
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
q=[]
h,w=map(int,input().split())
arr=[[True]*(w+2)]
for i in range(h):
  tmp=[True]
  for j in input():
    if j=='#':
      tmp.append(True)
    else:
      tmp.append(False)
  tmp.append(True)
  arr.append(tmp)
arr.append([True]*(w+2))
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j])
ans=0
while 1:
  nq=[]
  for y,x in q:
    if not arr[y-1][x]:
      nq.append([y-1,x])
      arr[y-1][x]=True
    if not arr[y][x-1]:
      nq.append([y,x-1])
      arr[y][x-1]=True
    if not arr[y+1][x]:
      nq.append([y+1,x])
      arr[y+1][x]=True
    if not arr[y][x+1]:
      nq.append([y,x+1])
      arr[y][x+1]=True
  if len(nq)==0:
    print(ans)
    break
  else:
    q=nq
    ans+=1

Submission status: Time Limit Exceeded

Solution code:
q=[]
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append(True)
for i in range(h):
  arr[i+1].append(True)
  for j in input():
    if j=='#':
      arr[i+1].append(True)
    else:
      arr[i+1].append(False)
  arr[i+1].append(True)
for i in range(w+2):
  arr[h+1].append(True)
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j])
ans=0
while 1:
  nq=[]
  for y,x in q:
    if not arr[y-1][x]:
      nq.append([y-1,x])
      arr[y-1][x]=True
    if not arr[y][x-1]:
      nq.append([y,x-1])
      arr[y][x-1]=True
    if not arr[y+1][x]:
      nq.append([y+1,x])
      arr[y+1][x]=True
    if not arr[y][x+1]:
      nq.append([y,x+1])
      arr[y][x+1]=True
  if len(nq)==0:
    print(ans)
    break
  else:
    q=nq
    ans+=1

Submission status: Time Limit Exceeded

Solution code:
q=[]
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append(True)
for i in range(h):
  arr[i+1].append(True)
  for j in input():
    if j=='#':
      arr[i+1].append(True)
    else:
      arr[i+1].append(False)
  arr[i+1].append(True)
for i in range(w+2):
  arr[h+1].append(True)
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j])
ans=0
while 1:
  nq=[]
  for y,x in q:
    for i in range(4):
      if not arr[y+dy[i]][x+dx[i]]:
        nq.append([y+dy[i],x+dx[i]])
        arr[y+dy[i]][x+dx[i]]=True
  if len(nq)==0:
    print(ans)
    break
  else:
    q=nq
    ans+=1

Submission status: Time Limit Exceeded

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append(True)
for i in range(h):
  arr[i+1].append(True)
  for j in input():
    if j=='#':
      arr[i+1].append(True)
    else:
      arr[i+1].append(False)
  arr[i+1].append(True)
for i in range(w+2):
  arr[h+1].append(True)
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j])
ans=0
while 1:
  nq=collections.deque()
  for y,x in q:
    for i in range(4):
      if not arr[y+dy[i]][x+dx[i]]:
        nq.append([y+dy[i],x+dx[i]])
        arr[y+dy[i]][x+dx[i]]=True
  if len(nq)==0:
    print(ans)
    break
  else:
    q=nq
    ans+=1

Submission status: Time Limit Exceeded

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append(True)
for i in range(h):
  arr[i+1].append(True)
  for j in input():
    if j=='#':
      arr[i+1].append(True)
    else:
      arr[i+1].append(False)
  arr[i+1].append(True)
for i in range(w+2):
  arr[h+1].append(True)
dx=[-1,0,1,0]
dy=[0,-1,0,1]
l=0
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j,0])
      l+=1
while 1:
  y,x,cnt=q.popleft()
  l-=1
  for i in range(4):
    if not arr[y+dy[i]][x+dx[i]]:
      q.append([y+dy[i],x+dx[i],cnt+1])
      l+=1
      arr[y+dy[i]][x+dx[i]]=True
  if l==0:
    print(cnt)
    break

Submission status: Time Limit Exceeded

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append(True)
for i in range(h):
  arr[i+1].append(True)
  for j in input():
    if j=='#':
      arr[i+1].append(True)
    else:
      arr[i+1].append(False)
  arr[i+1].append(True)
for i in range(w+2):
  arr[h+1].append(True)
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]:
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if not arr[y+dy[i]][x+dx[i]]:
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]=True
  if len(q)==0:
    print(cnt)
    break

Submission status: Time Limit Exceeded

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  l=0
  for j in input():
    arr[i+1].append(j)
    l+=1
    if j=='#':
      q.append([i+1,l,0])
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break

Submission status: Time Limit Exceeded

Solution code:
import collections
q=collections.deque()
h,w=map(int,input().split())
arr=[[] for _ in range(h+2)]
for i in range(w+2):
  arr[0].append('#')
for i in range(h):
  arr[i+1].append('#')
  for j in input():
    arr[i+1].append(j)
  arr[i+1].append('#')
for i in range(w+2):
  arr[h+1].append('#')
dx=[-1,0,1,0]
dy=[0,-1,0,1]
for i in range(1,h+1):
  for j in range(1,w+1):
    if arr[i][j]=='#':
      q.append([i,j,0])
while 1:
  y,x,cnt=q.popleft()
  for i in range(4):
    if arr[y+dy[i]][x+dx[i]]=='.':
      q.append([y+dy[i],x+dx[i],cnt+1])
      arr[y+dy[i]][x+dx[i]]='#'
  if len(q)==0:
    print(cnt)
    break

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a=[]
for i in range(h):
  a.append([it == '#' for it in input()])
q=[]
for i in range(h):
  for j in range(w):
    if a[i][j]: q.append((i, j))
cnt = -1
while q:
  cnt += 1
  r = []
  for i, j in q:
    if i > 0 and not a[i-1][j]:
      a[i-1][j]=True
      r += [(i-1, j)]
    if i < h-1 and not a[i+1][j]:
      a[i+1][j]=True
      r += [(i+1, j)]
    if j > 0 and not a[i][j-1]:
      a[i][j-1]=True
      r += [(i, j-1)]
    if j < w-1 and not a[i][j+1]:
      a[i][j+1]=True
      r += [(i, j+1)]
  q=r
print(cnt)

Submission status: Time Limit Exceeded

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

A=[]
for i in range(H):
  A.append(list(input()))
q=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      q.append((i, j))

cnt=0
while q:
  r=[]
  cnt += 1
  for i, j in q:
    if i-1 in range(H) and A[i-1][j] == '.':
      A[i-1][j] = '#'
      r += [(i-1, j)]
    if i+1 in range(H) and A[i+1][j] == '.':
      A[i+1][j] = '#'
      r.append((i+1, j))
    if j-1 in range(W) and A[i][j-1] == '.':
      A[i][j-1] = '#'
      q=r.append((i, j-1))
    if j+1 in range(W) and A[i][j+1] == '.':
      A[i][j+1] = '#'
      r.append((i, j+1))
  q=r
print(cnt-1)

Submission status: Time Limit Exceeded

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

A=[]
for i in range(H):
  A.append(list(input()))
q=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      q.append((i, j))

cnt=0
for _ in range(W*H):
  if not q: break
  r=[]
  for i, j in q:
    if i > 0 and A[i-1][j] == '.':
      A[i-1][j] = '#'
      r.append((i-1, j))
    if i < H-1 and A[i+1][j] == '.':
      A[i+1][j] = '#'
      r.append((i+1, j))
    if j > 0 and A[i][j-1] == '.':
      A[i][j-1] = '#'
      q=r.append((i, j-1))
    if j < W-1 and A[i][j+1] == '.':
      A[i][j+1] = '#'
      r.append((i, j+1))
  q=r
  cnt = cnt + 1
print(cnt-1)

Submission status: Time Limit Exceeded

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

A=[]
for i in range(H):
  A.append(list(input()))
q=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      q.append((i, j))

cnt=0
while q:
  r=[]
  for i, j in q:
    if i > 0 and A[i-1][j] == '.':
      A[i-1][j] = '#'
      r.append((i-1, j))
    if i < H-1 and A[i+1][j] == '.':
      A[i+1][j] = '#'
      r.append((i+1, j))
    if j > 0 and A[i][j-1] == '.':
      A[i][j-1] = '#'
      q=r.append((i, j-1))
    if j < W-1 and A[i][j+1] == '.':
      A[i][j+1] = '#'
      r.append((i, j+1))
  q=r
  cnt = cnt + 1
print(cnt-1)

Submission status: Time Limit Exceeded

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

A=[]
for i in range(H):
  A.append(list(input()))
q=deque(maxlen=H*W)
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      q.append((i, j, 0))

x=-1
while q:
  (i, j, n)=q.popleft()
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))
    
print(x)

Submission status: Time Limit Exceeded

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

A=[]
for i in range(H):
  A.append(list(input()))
q=deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      q.append((i, j, 0))

x=-1
while q:
  (i, j, n)=q.popleft()
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))
"""
q=deque([])
for i in range(W*H):
  q.append(i)
  q.append(i)
  q.append(i)
  q.append(i)
  q.popleft()
"""
print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int, input().split())
A=[]
for i in range(H):
  A.append(list(input()))
ds=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      ds.append((i, j))

x=-1
q=deque([(i, j, 0) for i,j in ds])
for i in range(H*W):
  if not q: break
  (i, j, n)=q.popleft()
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))

print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W=map(int, input().split())
A=[]
for i in range(H):
  A.append(list(input()))
ds=[]
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      ds.append((i, j))

x=-1
q=deque([(i, j, 0) for i, j in ds])
for i in range(H*W):
  if not q: break
  (i, j, n)=q.popleft()
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))

print(x)

Submission status: Time Limit Exceeded

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

x=-1
q=[(i, j, 0) for i, j in ds]
for i in range(H*W):
  if not q: break
  (i, j, n)=q[0]
  del q[0]
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))
  
#print(H,W)
#print(A)
#print(ds)
print(x)

Submission status: Time Limit Exceeded

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

x=-1
q=[(i, j, 0) for i, j in ds]
while(q):
  (i, j, n)=q[0]
  del q[0]
  x=max(x, n)
  if i > 0 and A[i-1][j] == '.':
    A[i-1][j] = '#'
    q.append((i-1, j, n+1))
  if i < H-1 and A[i+1][j] == '.':
    A[i+1][j] = '#'
    q.append((i+1, j, n+1))
  if j > 0 and A[i][j-1] == '.':
    A[i][j-1] = '#'
    q.append((i, j-1, n+1))
  if j < W-1 and A[i][j+1] == '.':
    A[i][j+1] = '#'
    q.append((i, j+1, n+1))

  
#print(H,W)
#print(A)
#print(ds)
print(x)

Submission status: Time Limit Exceeded

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

x=-1
q=[(p, 0) for p in ds]
while(q):
  (p, n)=q[0]
  #print(q)
  del q[0]
  x=max(x, n)
#  print(p, n)
  (i,j)=p
  A[i][j] = '#'
  if i > 0 and A[i-1][j] == '.': q.append(((i-1, j), n+1))
  if i < H-1 and A[i+1][j] == '.': q.append(((i+1, j), n+1))
  if j > 0 and A[i][j-1] == '.': q.append(((i, j-1), n+1))
  if j < W-1 and A[i][j+1] == '.': q.append(((i, j+1), n+1))

  
#print(H,W)
#print(A)
#print(ds)
print(x)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
L = []
for i in range(h):
  L.append(tuple(input()))
B = []
W = []
for i in range(h):
  for j in range(w):
    if L[i][j] == '.':
      W.append((i,j))
    else:
      B.append((i,j))
anslist = []
for i in range(len(W)):
  ans = float('inf')
  for j in range(len(B)):
    if ans >= abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1]):
      ans = abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1])
  anslist.append(ans)
if len(anslist) != 0:
  print(max(anslist))
else:
  print(0)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
L = []
for i in range(h):
  L.append(list(input()))
B = []
W = []
for i in range(h):
  for j in range(w):
    if L[i][j] == '.':
      W.append([i,j])
    else:
      B.append([i,j])
anslist = []
for i in range(len(W)):
  ans = float('inf')
  for j in range(len(B)):
    if ans >= abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1]):
      ans = abs(W[i][0]-B[j][0])+abs(W[i][1]-B[j][1])
  anslist.append(ans)
if len(anslist) != 0:
  print(max(anslist))
else:
  print(0)