Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    alter = inputs
    H = len(alter)
    W = len(alter[0])

    queue = deque([])
    reached_alter = []

    for y, line in enumerate(alter):
        a = []
        for x, mass in enumerate(line):
            if mass == "#":
                queue.append([x, y, 0])
                a.append(True)
            else:
                a.append(False)
        reached_alter.append(a)

    def is_continue(x, y):
        if x == -1 or y == -1 or x == W or y == H:
            return True
        if alter[y][x] == "#" or reached_alter[y][x]:
            return True
        reached_alter[y][x] = True
        return False

    last_count = 0
    while len(queue) > 0:
        [x, y, count] = queue.popleft()

        last_count = count

        if not is_continue(x - 1, y):
            queue.append([x - 1, y, count + 1])
        if not is_continue(x + 1, y):
            queue.append([x + 1, y, count + 1])
        if not is_continue(x, y - 1):
            queue.append([x, y - 1, count + 1])
        if not is_continue(x, y + 1):
            queue.append([x, y + 1, count + 1])

    return last_count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [H, W] = string_to_int(input())
    ret = solve(inputs(H))
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re


a = list(map(int,input().split()))

##  残りの行を取得する
b=[list(input()) for i in range(a[0])]

check_list=[]
remove=[]
for i in range(a[0]):
#  print(b[i])
  for j, x in enumerate(b[i]):
    if x == "#":
      check_list.append((i+1,j))
      check_list.append((i-1,j))
      check_list.append((i,j+1))
      check_list.append((i,j-1))
      remove.append((i,j))
      remove.append((i+1,j))
      remove.append((i-1,j))
      remove.append((i,j+1))
      remove.append((i,j-1))
#      print(j)

#print(check_list)

check_list_new=[]
count=0
while True:
  if not check_list:
    if not check_list_new:
      break 
    check_list = check_list_new
    check_list_new=[]
    check_list = set(check_list) - set(remove)
    count+=1

  c=check_list.pop()

  if c[0] < 0 or c[0] == a[0] or c[1] < 0 or c[1] == a[1] :
    continue
  if b[c[0]][c[1]] != "#":
    b[c[0]][c[1]] = "#"
    remove.append((c[0],c[1]))
    check_list_new.append((c[0]+1,c[1]))      
    check_list_new.append((c[0]-1,c[1]))      
    check_list_new.append((c[0],c[1]+1))      
    check_list_new.append((c[0],c[1]-1))   


print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re

a = list(map(int,input().split()))

##  残りの行を取得する
b=[list(input()) for i in range(a[0])]

check_list=[]

for i in range(a[0]):
#  print(b[i])
  for j, x in enumerate(b[i]):
    if x == "#":
      check_list.append((i+1,j))
      check_list.append((i-1,j))
      check_list.append((i,j+1))
      check_list.append((i,j-1))
#      print(j)

#print(check_list)

check_list_new=[]
count=0
while True:
  if not check_list:
    if not check_list_new:
      break 
    check_list = check_list_new
    check_list_new=[]
    count+=1

  c=check_list.pop()

  if c[0] < 0 or c[0] == a[0] or c[1] < 0 or c[1] == a[1] :
    continue
  if b[c[0]][c[1]] != "#":
    b[c[0]][c[1]] = "#"
    check_list_new.append((c[0]+1,c[1]))      
    check_list_new.append((c[0]-1,c[1]))      
    check_list_new.append((c[0],c[1]+1))      
    check_list_new.append((c[0],c[1]-1))   


print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class Cell:
    x = -1
    y = -1
    distance = -1

    def __init__(self, y, x, distance):
        self.x = x
        self.y = y
        self.distance = distance


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

ans = 0

outside = ["#" for x in range(W+2)]
C_list = [outside]

bfs = deque()

max_distance = 0

checked_list = [[0 for x in range(W+2)] for y in range(H+2)]

for i in range(1, H+1):
    A = input()
    for j in range(W+2):
        if j == 0:
            C_list.append([])
            C_list[i].append("#")
        elif j == W+1:
            C_list[i].append("#")
        else:
            C_list[i].append(A[j-1])
            if A[j-1] == "#":
                bfs.append(Cell(i, j, 0))
                checked_list[i][j] = 1

C_list.append(outside)


while len(bfs) > 0:
    cell = bfs.popleft()
    x = cell.x
    y = cell.y
    distance = cell.distance
    checked_list[y][x] = 1

    max_distance = max(max_distance, distance)

    if checked_list[y][x-1] == 0 and C_list[y][x-1] == ".":
        bfs.append(Cell(y, x-1, distance+1))
        checked_list[y][x - 1] = 2
    if checked_list[y][x+1] == 0 and C_list[y][x+1] == ".":
        bfs.append(Cell(y, x+1, distance+1))
        checked_list[y][x + 1] = 2
    if checked_list[y-1][x] == 0 and C_list[y-1][x] == ".":
        bfs.append(Cell(y-1, x, distance+1))
        checked_list[y-1][x] = 2
    if checked_list[y+1][x] == 0 and C_list[y+1][x] == ".":
        bfs.append(Cell(y+1, x, distance+1))
        checked_list[y+1][x] = 2

print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

starts = []
H, W = map(int, input().split())
HW = H * W
A = [list(input()) for i in range(H)]

AA = copy.deepcopy(A)
q = deque()

for i in range(H):
    for j in range(W):
        if AA[i][j] == "#":
            AA[i][j] = 0
            q.append((i,j))
        else:
            AA[i][j] = HW
dr = [(1,0),(-1,0),(0,1),(0,-1)]

while len(q):
    r = q.popleft()
    x = r[1]
    y = r[0]
    now = AA[y][x]
    for d in range(4):
        nx = x + dr[d][0]
        ny = y + dr[d][1]
        if 0 <= nx < W and 0 <= ny < H:
            a = AA[ny][nx]
            if a == HW:
                q.append((ny,nx))
                AA[ny][nx] = min(now+1, a)
                   
print(max([max(AA[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

starts = []
H, W = map(int, input().split())
HW = H * W
A = [list(input()) for i in range(H)]

AA = copy.deepcopy(A)
q = deque()

for i in range(H):
    for j in range(W):
        if AA[i][j] == "#":
            AA[i][j] = 0
            q.append((i,j))
        else:
            AA[i][j] = HW
dr = [(1,0),(-1,0),(0,1),(0,-1)]
while len(q):
    r = q.popleft()
    x = r[1]
    y = r[0]
    now = AA[y][x]
    for d in range(4):
        nx = x + dr[d][0]
        ny = y + dr[d][1]
        if 0 <= nx < W and 0 <= ny < H:
            if A[ny][nx] != "#" and AA[ny][nx] == HW:
                q.append((ny,nx))
                AA[ny][nx] = min(now+1, AA[ny][nx])
                   
print(max([max(AA[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

starts = []
H, W = map(int, input().split())
HW = H * W
A = [list(input()) for i in range(H)]

AA = copy.deepcopy(A)
B = copy.deepcopy(A)

for i in range(H):
    for j in range(W):
        if AA[i][j] == "#":
            AA[i][j] = 0
            starts.append((i,j))
        else:
            AA[i][j] = HW
            
for i in starts:
    ckd = [[0] * W for i in range(H)]
    q = deque()
    q.append(i)
    dr = [(1,0),(-1,0),(0,1),(0,-1)]
    while len(q):
        r = q.popleft()
        x = r[1]
        y = r[0]
        now = ckd[y][x]
        for d in range(4):
            nx = x + dr[d][0]
            ny = y + dr[d][1]
            if 0 <= nx < W and 0 <= ny < H:
                if A[ny][nx] != "#" and ckd[ny][nx] == 0:
                    q.append((ny,nx))
                    ckd[ny][nx] = now+1
                    AA[ny][nx] = min(now+1, AA[ny][nx])
                    
print(max([max(AA[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[input() for i in range(h)]
t=[[10000]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            t[i][j]=0
flg=True
step=1
ans=0
while flg:
    flg=False
    for i in range(h):
        for j in range(w):
            if t[i][j]==step-1:
                if i-1>=0:
                    if t[i-1][j]>step:
                        t[i-1][j]=step
                        flg=True
                if i+1<h:
                    if t[i+1][j]>step:
                        t[i+1][j]=step
                        flg=True
                if j-1>=0:
                    if t[i][j-1]>step:
                        t[i][j-1]=step
                        flg=True
                if j+1<w:
                    if t[i][j+1]>step:
                        t[i][j+1]=step
                        flg=True
    if flg:
        ans=step
        step+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for dx,dy in moves:
    for x,y in q:
      xx = x+dx
      yy = y+dy
      if not visited[xx][yy]:
        visited[xx][yy] = True
        qq.append((xx,yy))
  q = qq
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    for dx,dy in moves:
      xx = x+dx
      yy = y+dy
      if not visited[xx][yy]:
        visited[xx][yy] = True
        qq.append((xx,yy))
  q = qq
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)] + [[True]+[False]*W+[True] for _ in range(H)] + [[True]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      visited[i][j] = True
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    for dx,dy in moves:
      xx = x+dx
      yy = y+dy
      if not visited[xx][yy]:
        visited[xx][yy] = True
        qq.append((xx,yy))
  q = qq
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)] + [[True]+[False]*W+[True] for _ in range(H)] + [[True]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      visited[i][j] = True
      q.append((i,j))

ans = -1
qq = []
while q:
  ans += 1
  for x,y in q:
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
      xx = x+dx
      yy = y+dy
      if not visited[xx][yy]:
        visited[xx][yy] = True
        qq.append((xx,yy))
  q = qq
  qq = []
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

d = [[0]*(W+2)] + [[0]+[INF]*W+[0] for _ in range(H)] + [[0]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      d[i][j] = 0
      q.append((i,j))

ans = -1
qq = []
while q:
  ans += 1
  for x,y in q:
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
      xx = x+dx
      yy = y+dy
      if d[xx][yy] == INF:
        d[xx][yy] = 0
        qq.append((xx,yy))
  q = qq
  qq = []
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

d = [[0]*(W+2)] + [[0]+[INF]*W+[0] for _ in range(H)] + [[0]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

ans = 0
qq = []
while q:
  for dv,x,y in q:
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
      xx = x+dx
      yy = y+dy
      if d[xx][yy] == INF:
        d[xx][yy] = dv+1
        ans = dv+1
        qq.append((dv+1,xx,yy))
  q = qq
  qq = []
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

H,W = map(int,input().split())
INF = 10**18
q = deque()

d = [[0]*(W+2)] + [[0]+[INF]*W+[0] for _ in range(H)] + [[0]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

ans = 0
qq = []
while q:
  for dv,x,y in q:
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
      xx = x+dx
      yy = y+dy
      if d[xx][yy] == INF:
        d[xx][yy] = dv+1
        ans = dv+1
        qq.append((dv+1,xx,yy))
  q = qq
  qq = []
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

H,W = map(int,input().split())
INF = 10**18
q = deque()

d = [[0]*(W+2)] + [[0]+[INF]*W+[0] for _ in range(H)] + [[0]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

      
ans = 0
while q:
  dv,x,y = q.popleft()
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      q.append((dv+1,xx,yy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
from collections import deque

H,W = map(int,input().split())
INF = 10**18
q = deque()

d = [[INF]*W for _ in range(H)] # '#'からの距離

for i in range(H):
  for j,c in enumerate(input()):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

      
ans = 0
while q:
  dv,x,y = q.popleft()
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      q.append((dv+1,xx,yy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**6)
from collections import deque

H,W = map(int,input().split())
INF = 10**18
q = deque()

d = [[INF]*W for _ in range(H)] # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

      
ans = 0
while q:
  dv,x,y = q.popleft()
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      q.append((dv+1,xx,yy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = [[INF]*W for _ in range(H)] # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i][j] = 0
      heapq.heappush(q,(0,i,j))

      
ans = 0
while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = [[INF]*W for _ in range(H)] # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i][j] = 0
      heapq.heappush(q,(0,i,j))

      
ans = 0
while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]
graph = [[float('inf')] * W for _ in range(H)]
deq = deque()

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            graph[i][j] = 0
            deq.append((i, j))

while deq:
    x, y = deq.popleft()
    for i, j in offsets:
        if (not 0 <= x + i < H) or (not 0 <= y + j < W):
            continue

        if graph[x + i][y + j] < float('inf'):
            continue

        if grid[x + i][y + j] == '#':
            continue
            
        graph[x + i][y + j] = graph[x][y] + 1
        deq.append((x + i, y + j))
        
print(max(max(v) for v in graph))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":

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

    q = []
    reached = [[True]*(w+2)]
    for i in range(1, h+1):
      reached.append([True] + [s == '#' for s in list(input())] + [True])
      for j in range(1,w+1):
        if reached[i][j]: q.append((i,j))
    reached.append([True]*(w+2))

    res = 0
    while 1:
      qq = []
      for k,l in q:
        if not reached[k+1][l]:
          qq.append((k+1, l))
          reached[k+1][l] = True
        if not reached[k][l+1]:
          qq.append((k, l+1))
          reached[k][l+1] = True
        if not reached[k-1][l]:
          qq.append((k-1, l))
          reached[k-1][l] = True
        if not reached[k][l-1]:
          qq.append((k, l-1))
          reached[k][l-1] = True
      if len(qq) == 0:
        break
      else:
        pass
      
      q = qq
      res += 1

    print(res)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":

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

    q = []
    reached = [[True]*(w+2)]
    for i in range(1, h+1):
      reached.append([True] + [s == '#' for s in list(input())] + [True])
      for j in range(1,w+1):
        if reached[i][j]: q.append((i,j))
    reached.append([True]*(w+2))

    res = 0
    head = 0
    tail = len(q)
    count = len(q)
    i = 0
    while tail - head > 0:
        k = q[head][0]
        l = q[head][1]
        if not reached[k+1][l]:
            q.append((k+1, l))
            reached[k+1][l] = True
            tail += 1
        if not reached[k][l+1]:
            q.append((k, l+1))
            reached[k][l+1] = True
            tail += 1
        if not reached[k-1][l]:
            q.append((k-1, l))
            reached[k-1][l] = True
            tail += 1
        if not reached[k][l-1]:
            q.append((k, l-1))
            reached[k][l-1] = True
            tail += 1

        head += 1
        i += 1
        if i == count and tail - head > 0:
            count = tail - head
            i = 0
            res += 1
        else:
            pass

    print(res)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":

    h,w = list(map(int,input().split()))
    a = [None]*h
    for i in range(h): a[i] = input()

    reached = [[True]*(w+2)]
    for i in range(1, h+1): reached.append([True] + [False]*w + [True])
    reached.append([True]*(w+2))

    q = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append([i+1, j+1])
                reached[i+1][j+1] = True

    res = 0
    head = 0
    tail = len(q)
    count = len(q)
    i = 0
    while tail - head > 0:
        k = q[head][0]
        l = q[head][1]
        if not reached[k+1][l]:
            q.append([k+1, l])
            reached[k+1][l] = True
            tail += 1
        if not reached[k][l+1]:
            q.append([k, l+1])
            reached[k][l+1] = True
            tail += 1
        if not reached[k-1][l]:
            q.append([k-1, l])
            reached[k-1][l] = True
            tail += 1
        if not reached[k][l-1]:
            q.append([k, l-1])
            reached[k][l-1] = True
            tail += 1

        head += 1
        i += 1
        if i == count and tail - head > 0:
            count = tail - head
            i = 0
            res += 1
        else:
            pass

    print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

if __name__ == "__main__":

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

    a = [[None]]*h
    for i in range(h): a[i] = input()

    reached = [[True]*(w+2) for i in range(h+2)]
    for i in range(1, h+1): reached[i][1:-1] = [False]*w

    q = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                q.append([i+1, j+1])
                reached[i+1][j+1] = True

    res = 0
    head = 0
    tail = len(q)
    count = len(q)
    i = 0
    while tail - head > 0:
        k = q[0][0]
        l = q[0][1]
        if not reached[k+1][l]:
            q.append([k+1,l])
            reached[k+1][l] = True
            tail += 1
        if not reached[k][l+1]:
            q.append([k,l+1])
            reached[k][l+1] = True
            tail += 1
        if not reached[k-1][l]:
            q.append([k-1,l])
            reached[k-1][l] = True
            tail += 1
        if not reached[k][l-1]:
            q.append([k,l-1])
            reached[k][l-1] = True
            tail += 1

        tail -= 1
        i += 1
        q.popleft()
        if i == count and tail - head > 0:
            count = tail
            i = 0
            res += 1
        else:
            pass

    print(res)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":

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

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

    reached = [[True for i in range(w+2)] for j in range(h+2)]
    for i in range(1, h+1): reached[i][1:-1] = [False for i in range(w)]

    queue = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                queue.append([i+1, j+1])
                reached[i+1][j+1] = True

    res = 0
    head = 0
    tail = len(queue)
    count = len(queue)
    i = 0
    while tail - head > 0:
        k = queue[0][0]
        l = queue[0][1]
        if not reached[k+1][l]:
            queue.append([k+1,l])
            reached[k+1][l] = True
            tail += 1
        if not reached[k][l+1]:
            queue.append([k,l+1])
            reached[k][l+1] = True
            tail += 1
        if not reached[k-1][l]:
            queue.append([k-1,l])
            reached[k-1][l] = True
            tail += 1
        if not reached[k][l-1]:
            queue.append([k,l-1])
            reached[k][l-1] = True
            tail += 1

        tail -= 1
        i += 1
        queue.pop(0)
        if i == count and tail - head > 0:
            count = tail
            i = 0
            res += 1
        else:
            pass

    print(res)

Submission status: Time Limit Exceeded

Solution code:
h, w=map(int, input().split())
a=[]
need_visited=[[0 for i in range(w)] for j in range(h)]
stack=[]
for i in range(h):
    a.append(list(input()))

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



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


while len(stack)!=0:
    now_point=stack.pop(0)
    for i in range(4):
        target_h=now_point[0]+dx[i]
        target_w=now_point[1]+dy[i]
        if 0<=target_h<h and 0<=target_w<w:
            if a[target_h][target_w]==".":
                need_visited[target_h][target_w]=need_visited[now_point[0]][now_point[1]]+1
                a[target_h][target_w]="#"
                stack.append([target_h, target_w])
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans, need_visited[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w=map(int, input().split())
a=[]
need_visited=[[0 for i in range(w)] for j in range(h)]
stack=[]
for i in range(h):
    a.append(list(input()))

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



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


while len(stack)!=0:
    now_point=stack.pop(0)
    now_y=now_point[0]
    now_x=now_point[1]
    for i in range(4):
        if 0<=now_x+dx[i]<=w-1 and 0<=now_y+dy[i]<=h-1:
            if a[now_y+dy[i]][now_x+dx[i]]==".":
                need_visited[now_y+dy[i]][now_x+dx[i]]=need_visited[now_y][now_x]+1
                a[now_y+dy[i]][now_x+dx[i]]="#"
                stack.append([now_y+dy[i], now_x+dx[i]])
max_list=[]
for i in range(h):
    max_list.append(max(need_visited[i]))
print(max(max_list))

Submission status: Time Limit Exceeded

Solution code:
h, w=map(int, input().split())
a=[]
visited=[[True for i in range(w)] for j in range(h)]
need_visited=[[0 for i in range(w)] for j in range(h)]
stack=[]
for i in range(h):
    a.append(list(input()))

for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            stack.append([i, j])
            visited[i][j]=False



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


while len(stack)!=0:
    now_point=stack.pop(0)
    now_y=now_point[0]
    now_x=now_point[1]
    for i in range(4):
        if 0<=now_x+dx[i]<=w-1 and 0<=now_y+dy[i]<=h-1:
            if a[now_y+dy[i]][now_x+dx[i]]==".":
                if visited[now_y+dy[i]][now_x+dx[i]]:
                    need_visited[now_y+dy[i]][now_x+dx[i]]=need_visited[now_y][now_x]+1
                    visited[now_y+dy[i]][now_x+dx[i]]=False

                    stack.append([now_y+dy[i], now_x+dx[i]])
max_list=[]
for i in range(h):
    max_list.append(max(need_visited[i]))
print(max(max_list))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
  h,w = list(map(int,input().split()))
  a = [["*"*w] for i in range(h)]
  reached = [[-1 for i in range(w)] for j in range(h)]
  for i in range(h): a[i] = input()
  
  queue = []
  for i in range(h):
    for j in range(w):
      if a[i][j] == "#":
        queue.append([i,j])
        reached[i][j] = 0
  
  res = 0
  while len(queue) > 0:
    for i in range(len(queue)):
      k = queue[0][0]
      l = queue[0][1]
      if 0 <= k+1 < h and 0 <= l < w and reached[k+1][l] == -1:
          queue.append([k+1, l])
      if 0 <= k < h and 0 <= l+1 < w and reached[k][l+1] == -1:
          queue.append([k, l+1])
      if 0 <= k-1 < h and 0 <= l < w and reached[k-1][l] == -1:
          queue.append([k-1, l])
      if 0 <= k < h and 0 <= l-1 < w and reached[k][l-1] == -1:
          queue.append([k, l-1])
      reached[k][l] = res
      queue.pop(0)
    
    res += 1
  
  print(res-1)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
  h,w = list(map(int,input().split()))
  a = [["*"*w] for i in range(h)]
  reached = [[-1 for i in range(w)] for j in range(h)]
  for i in range(h): a[i] = input()
  
  queue = []
  for i in range(h):
    for j in range(w):
      if a[i][j] == "#":
        queue.append([i,j])
        reached[i][j] = 0
  
  res = 0
  while len(queue) > 0:
    k = queue[0][0]
    l = queue[0][1]
    p = reached[k][l] + 1
    if 0 <= k+1 < h and 0 <= l < w:
      if reached[k+1][l] == -1:
        reached[k+1][l] = p
        res = p
        queue.append([k+1, l])
    if 0 <= k < h and 0 <= l+1 < w:
      if reached[k][l+1] == -1:
        reached[k][l+1] = p
        res = p
        queue.append([k, l+1])
    if 0 <= k-1 < h and 0 <= l < w:
      if reached[k-1][l] == -1:
        reached[k-1][l] = p
        res = p
        queue.append([k-1, l])
    if 0 <= k < h and 0 <= l-1 < w:
      if reached[k][l-1] == -1:
        reached[k][l-1] = p
        res = p
        queue.append([k, l-1])
    queue.pop(0)
  print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = deque()
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w, 0])

ans = 0
while len(painted) > 0:
    blackcell = painted.popleft()
    for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
        nh = blackcell[0] + dy
        nw = blackcell[1] + dx
        d = blackcell[2]
        if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
            cell[nh][nw] = '#'
            painted.append([nh, nw, d + 1])
        ans = d

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split()]
cell = [list(input()) for i in range(H)]

painted = []
for h in range(H):
    for w in range(W):
        if cell[h][w] == '#':
            painted.append([h, w])

ans = 0
while len(painted) > 0:
    to_be_painted = []
    for blackcell in painted:
        h = blackcell[0]
        w = blackcell[1]
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh and nh < H and 0 <= nw and nw < W and cell[nh][nw] == '.':
                cell[nh][nw] = '#'
                to_be_painted.append([nh, nw])
    painted = to_be_painted
    if len(painted) > 0: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=[list(input()) for i in range(h)]
q,x=[],-1
for i in range(h):
    for j in range(w):
        if l[i][j]=="#":q.append([i,j])
while len(q)>0:
    x+=1
    qi=[]
    for a in q:
        i,j=a
        if i>0 and l[i-1][j]==".":
            l[i-1][j]=x+1
            qi.append([i-1,j])
        if i<h-1 and l[i+1][j]==".":
            l[i+1][j]=x+1
            qi.append([i+1,j])
        if j>0 and l[i][j-1]==".":
            l[i][j-1]=x+1
            qi.append([i,j-1])
        if j<w-1 and l[i][j+1]==".":
            l[i][j+1]=x+1
            qi.append([i,j+1])
    q=qi[:]
print(x)