Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

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

def bfs(d):
    m = 0
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                m = max(m,d[ny][nx])
                q.append([ny,nx])
    return m

m = bfs(d)
print(m)

Submission status: Time Limit Exceeded

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

from collections import deque

def myinput():
    return map(int,readline().split())

h,w = myinput()
field = [ list(input()) for _ in range(h) ]

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

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

def bfs(d):
    m = 0
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                m = max(m,d[ny][nx])
                q.append([ny,nx])
    return m

m = bfs(d)
print(m)

Submission status: Time Limit Exceeded

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

from collections import deque

def myinput():
    return map(int,readline().split())

h,w = myinput()
field = [ list(input()) for _ in range(h) ]

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

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

def bfs(d):
    m = 0
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                m = max(m,d[ny][nx])
                q.append([ny,nx])
    return d,m

d,m = bfs(d)
print(m)

Submission status: Time Limit Exceeded

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

from collections import deque
import numpy as np

def myinput():
    return map(int,readline().split())

h,w = myinput()
field = [ list(input()) for _ in range(h) ]

d = [ [float("inf")]*w for _ in range(h) ]
q = deque()

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

def bfs(d):
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                q.append([ny,nx])
    return d

d2 = bfs(d)
d3 = np.array(d2)
ans = np.max(d3)
print(ans)

Submission status: Time Limit Exceeded

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

from collections import deque
import copy
import numpy as np

def myinput():
    return map(int,readline().split())

def mycol(data,col):
    return [ row[col] for row in data ]

h,w = myinput()
field = [ list(input()) for _ in range(h) ]
# print(field)

d = [ [float("inf")]*w for _ in range(h) ]

q = deque()

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

# print(q)

def bfs(d):
    while q:
        y,x = q.popleft()
        for j,i in ([1,0],[0,-1],[-1,0],[0,1]):
            ny = y + j
            nx = x + i
            if ny==-1 or nx==-1 or ny==h or nx==w:
                pass
            elif field[ny][nx]=="#":
                pass
            elif d[ny][nx]!=float("inf"):
                pass
            else:
                field[ny][nx] = "#"
                d[ny][nx] = d[y][x] + 1
                q.append([ny,nx])
    return d

d2 = bfs(d)

# print(d2)

d3 = np.array(d2)
ans = np.max(d3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue 

H,W = map(int, input().split())
n_b = 0
m=[]
q = queue.Queue()

for i in range(H):
  m.append(list(input()))
  for j in range(W):
    if m[i][j]=="#":
      n_b += 1
      # q.put([i,j])

n=0

import numpy as np
yet_m=np.zeros([H,W])

while n_b != H*W:
  for i in range(H):
    for j in range(W):
      if m[i][j]=="#" and yet_m[i][j]==0:
        # print("{} {}".format(i,j))
        q.put([i,j])
        yet_m[i][j]=1

  while not q.empty():
    k,l=q.get()
    if l>0:
      if m[k][l-1]==".":
        m[k][l-1]="#"
        n_b+=1
    if l <W-1:
      if m[k][l+1]==".":
        m[k][l+1]="#"
        n_b+=1
    if k>0:
      if m[k-1][l]==".":
        m[k-1][l]="#"
        n_b+=1
    if k<H-1:
      if m[k+1][l]==".":
        m[k+1][l]="#"
        n_b+=1
  n+=1

print(n)

Submission status: Time Limit Exceeded

Solution code:
import queue 

H,W = map(int, input().split())
n_b = 0
m=[]
q = queue.Queue()

for i in range(H):
  m.append(list(input()))
  for j in range(W):
    if m[i][j]=="#":
      n_b += 1
      q.put([i,j])

n=0

import numpy as np
yet_m=np.zeros([H,W])

while n_b != H*W:
  for i in range(H):
    for j in range(W):
      if m[i][j]=="#" and yet_m[i][j]==0:
        # print("{} {}".format(i,j))
        q.put([i,j])
        yet_m[i][j]=1

  while not q.empty():
    k,l=q.get()
    if l>0:
      if m[k][l-1]==".":
        m[k][l-1]="#"
        n_b+=1
    if l <W-1:
      if m[k][l+1]==".":
        m[k][l+1]="#"
        n_b+=1
    if k>0:
      if m[k-1][l]==".":
        m[k-1][l]="#"
        n_b+=1
    if k<H-1:
      if m[k+1][l]==".":
        m[k+1][l]="#"
        n_b+=1
  n+=1

print(n)

Submission status: Time Limit Exceeded

Solution code:
import queue 

H,W = map(int, input().split())
n_b = 0
m=[]
q = queue.Queue()

for i in range(H):
  m.append(list(input()))
  for j in range(W):
    if m[i][j]=="#":
      n_b += 1
      q.put([i,j])

n=0

while n_b != H*W:
  for i in range(H):
    for j in range(W):
      if m[i][j]=="#":
        # print("{} {}".format(i,j))
        q.put([i,j])

  while not q.empty():
    k,l=q.get()
    if l>0:
      if m[k][l-1]==".":
        m[k][l-1]="#"
        n_b+=1
    if l <W-1:
      if m[k][l+1]==".":
        m[k][l+1]="#"
        n_b+=1
    if k>0:
      if m[k-1][l]==".":
        m[k-1][l]="#"
        n_b+=1
    if k<H-1:
      if m[k+1][l]==".":
        m[k+1][l]="#"
        n_b+=1
  n+=1

print(n)

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())
    board = [input().strip() for i in range(H)]
    check = [[False] * W for i in range(H)]

    q = deque()
    for y in range(H):
        for x in range(W):
            if board[y][x] == "#":
                q.append((0, x, y))
                check[y][x] = True
    
    ans = 0
    while len(q) > 0:
        cost, x, y = q.popleft()
        ans = max(ans, cost)
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if board[ny][nx] == "." and not check[ny][nx]:
                    q.append((cost+1, nx, ny))
                    check[ny][nx] = True
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())
    board = [input().strip() for i in range(H)]
    min_ = [[int(1e5)] * W for i in range(H)]

    q = deque()
    for y in range(H):
        for x in range(W):
            if board[y][x] == "#":
                q.append((0, x, y))
                min_[y][x] = 0
    
    ans = 0
    while len(q) > 0:
        cost, x, y = q.popleft()
        min_[y][x] = cost
        ans = max(ans, cost)
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if board[ny][nx] == "." and cost + 1 < min_[ny][nx]:
                    q.append((cost+1, nx, ny))
                    min_[ny][nx] = cost+1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())
    board = [input().strip() for i in range(H)]
    min_ = [[int(1e5)] * W for i in range(H)]

    q = deque()
    for y in range(H):
        for x in range(W):
            if board[y][x] == "#":
                q.append((0, x, y))
    
    ans = 0
    while len(q) > 0:
        cost, x, y = q.popleft()
        if cost < min_[y][x]:
            min_[y][x] = cost
            ans = max(ans, cost)
            for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
                if 0 <= nx and nx < W and 0 <= ny and ny < H:
                    if board[ny][nx] == ".":
                        q.append((cost+1, nx, ny))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    V = set()
    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": q.append((h, w, 0))
    Ans = -1
    S = ((-1, 0), (0, 1), (1, 0), (0, -1))
    while q:
        h, w, d = q.popleft()
        if (h, w) not in V:
            V |= {(h, w)}
            Ans = d
            for dh, dw in S:
                if 0 <= h + dh < H and 0 <= w + dw < W:
                  	if (h+dh, w+dw) not in V: q.append((h+dh, w+dw, d+1))
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
f = [input() for _ in range(h)]
ss = []
def bfs(l):
    stack = l
    visited = [[0]*w for i in range(h)]
    dist = [[10**8]*w for i in range(h)]
    vec = [(0,1),(1,0),(-1,0),(0,-1)]
    for sx,sy in l:dist[sx][sy] = 0
    while stack:
        next = []
        for now in stack:
            x,y = now[0],now[1]
            visited[x][y] = 1
            for tx,ty in vec:
                nx,ny = x+tx,y+ty
                if nx < 0 or ny < 0 or nx>h-1 or ny > w-1:continue
                if visited[nx][ny] :continue
                if f[nx][ny] == '#':continue
                next.append((nx,ny))
                dist[nx][ny] = min(dist[nx][ny],dist[x][y] +1)
            stack = next
    res  = 0
    for i in range(h):
        for j in range(w):
            if dist[i][j] == 10**8:continue
            res = max(res,dist[i][j])
    return res


for i in range(h):
    for j in range(w):
        if f[i][j] == '#':ss.append((i,j))
ans  = bfs(ss)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                que.append((i, j))
                a[i][j] = 0

    while que:
        p = que.popleft()
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]

            if 0 <= nx < w and 0 <= ny < h and a[ny][nx] == '.':
                que.append((ny,nx))
                a[ny][nx] = a[p[0]][p[1]] + 1
    ans = 0
    for i in range(h):
        ans = max(ans, *a[i])
    return ans

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():

    from collections import deque

    H, W = map(int, input().split())
    maze = [input() for i in range(H)]
    start_list=[]
    for i in range(H):
        for j in range(W):
            if maze[i][j]=='#':
                start_list.append([i,j])
    INF = 10 ** 20

    visited = [[INF] * W for j in range(H)]


    def bfs(maze):
        queue = deque()
        for [i,j] in start_list:
            queue.append([i,j])
            visited[i][j]=0
        while queue:
            y, x = queue.popleft()
            cnt=0
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y + j, x + k
                if 0 <= ny < H and 0 <= nx < W and \
                        maze[ny][nx] == "." and visited[ny][nx]==INF:
                        visited[ny][nx] = visited[y][x] + 1
                        queue.append([ny, nx])
        return visited

    bfs(maze)
    print(np.amax(visited))


resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    Dist = [[False] * W for _ in range(H)]
    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": q.append((h, w, 0))
    Ans = -1
    S = ((-1, 0), (0, 1), (1, 0), (0, -1))
    while q:
        h, w, d = q.popleft()
        if not Dist[h][w]:
            Dist[h][w] = True
            Ans = max(d, Ans)
            for dh, dw in S:
                if 0 <= h + dh < H and 0 <= w + dw < W and not Dist[h+dh][w+dw]:
                    q.append((h+dh, w+dw, d+1))
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [input().strip("\n") for _ in range(H)]
    Dist = [[-1] * W for _ in range(H)]
    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#": q.append((h, w, 0))
    Ans = -1
    S = ((-1, 0), (0, 1), (1, 0), (0, -1))
    while q:
        h, w, d = q.popleft()
        if Dist[h][w] == -1:
            Dist[h][w] = 0
            Ans = max(d, Ans)
            for dh, dw in S:
                if 0 <= h + dh < H and 0 <= w + dw < W and Dist[h+dh][w+dw] == -1:
                    q.append((h+dh, w+dw, d+1))
    print(Ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

while white:
    white = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == '.':
                white = 1
            if a[i][j] == '#':
                for k in range(4):
                    ny = i + dy[k]
                    nx = j + dx[k]
                    if 0 <= ny < h and 0 <= nx < w:
                        b[ny][nx] = '#'
    ans += 1
    a = copy.deepcopy(b)

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))

h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
dis = [[inf] * w for i in range(h)]
import heapq
def bfs(start_set):
  que = []
  for si,sj in start_set:
    que.append((0,si,sj))
    dis[si][sj] = 0
  while que:
    cost,i,j = heapq.heappop(que)
    if dis[i][j] < cost: continue
    for di,dj in dydx4:
      ni = i + di
      nj = j + dj
      if not (0 <= ni < h and 0 <= nj < w):continue
      if A[ni][nj] == "#":continue
      # if A[ni][nj] == "#" and dis[ni][nj] == inf:
      #   dis[ni][nj] = 0
      #   heapq.heappush(que,(0,ni,nj))
      if cost + 1 < dis[ni][nj]: 
        dis[ni][nj] = cost+1
        que.append((cost+1,ni,nj))

start_set = []
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      start_set.append((i,j))
bfs(start_set)
      
print(max(map(max,dis)))

Submission status: Time Limit Exceeded

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

#dp[i][j]=最も近い黒マスまでの最小マンハッタン距離
INF=10**9
dp = [[INF] * W for _ in range(H)]

#黒マスを起点にDFS
def dfs(si,sj):
    dp[si][sj] = 0
    stk = [(si,sj,0)]
    while stk:
        i,j,d = stk.pop()
        for di,dj in ((1,0),(-1,0),(0,1),(0,-1)):
            ti,tj,td = i+di,j+dj,d+1
            if (not 0<=ti<H) or (not 0<=tj<W): continue
            if dp[ti][tj] <= td: continue
            if A[ti][tj] == '#': td = 0
            dp[ti][tj] = td
            stk.append((ti,tj,td))

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dfs(i,j)
            break

ans=0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

minDist = [[10**10] * W for _ in range(H)]
while que:
    h, w, d = que.popleft()

    if minDist[h][w] <= d:
        continue
    minDist[h][w] = d

    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= dh + h < H and 0 <= dw + w < W:
            que.append((dh + h, dw + w, d + 1))

ans = max(max(d) for d in minDist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))

h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
dis = [[inf] * w for i in range(h)]
import heapq
def bfs(si,sj):
  que = []
  que.append((0,si,sj))
  dis[si][sj] = 0
  while que:
    cost,i,j = heapq.heappop(que)
    if dis[i][j] < cost: continue
    for di,dj in dydx4:
      ni = i + di
      nj = j + dj
      if not (0 <= ni < h and 0 <= nj < w):continue
      if A[ni][nj] == "#" and dis[ni][nj] == inf:
        dis[ni][nj] = 0
        heapq.heappush(que,(0,ni,nj))
      if cost + 1 < dis[ni][nj]: 
        dis[ni][nj] = cost+1
        que.append((cost+1,ni,nj))
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      bfs(i,j)
      break
  else:continue
  break
print(max(map(max,dis)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
dydx4 = ((-1,0),(0,-1),(0,1),(1,0))

h,w = map(int,input().split())
A = [list(input()) for i in range(h)]
dis = [[inf] * w for i in range(h)]
def bfs(si,sj):
  que = collections.deque()
  que.append((0,si,sj))
  dis[si][sj] = 0
  while que:
    cost,i,j = que.popleft()
    for di,dj in dydx4:
      ni = i + di
      nj = j + dj
      if not (0 <= ni < h and 0 <= nj < w):continue
      if A[ni][nj] == "#":continue
      if cost + 1 < dis[ni][nj]:
        dis[ni][nj] = cost+1
        que.append((cost+1,ni,nj))
for i in range(h):
  for j in range(w):
    if A[i][j] == "#":
      bfs(i,j)
print(max(map(max,dis)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
gridgraph = [list(input()) for _ in range(H)]
distance = [[float("inf")]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append([i, j])
            distance[i][j] = 0
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while len(q):
    cy, cx = q.popleft()
    for dy, dx in adjacent:
        ny, nx = cy+dy, cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if distance[ny][nx] != float("inf"):
            continue
        distance[ny][nx] = distance[cy][cx] + 1
        q.append([ny, nx])
ans = 0
for d in distance:
    ans = max(ans, max(d))
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    H, W = map(int, input().split())

    m = [list(map(lambda x: 1 if x=="#" else 0, input())) for _ in range(H)]
    black = [(i, j, 0) for i in range(H) for j in range(W) if m[i][j] == 1]

    # print(m)
    # print(black)

    queue = deque(black)
    queue_append = queue.append
    ans = 0
    while queue:
        p = queue.popleft()
        if ans < p[2]:
            ans += 1
        for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    queue_append((next_p[0], next_p[1], ans+1))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

m = [list(map(lambda x: 1 if x=="#" else 0, input())) for _ in range(H)]
black = [(i, j, 0) for i in range(H) for j in range(W) if m[i][j] == 1]

# print(m)
# print(black)

queue = deque(black)
queue_append = queue.append
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue_append((next_p[0], next_p[1], ans+1))
print(ans)

Submission status: Time Limit Exceeded

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

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

m = [[0 for _ in range(W)] for _ in range(H)]
black = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            black.append((i, j, 0))

# print(m)
# print(root)

queue = deque(black)
ans = 0
while queue:
    p = queue.popleft()
    if ans < p[2]:
        ans += 1
    for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
        next_p = (p[0] + i, p[1] + j)
        if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
            if not m[next_p[0]][next_p[1]]:
                m[next_p[0]][next_p[1]] = 1
                queue.append((next_p[0], next_p[1], ans+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [False] * (w * h)
  dq = deque()
  for i in range(h):
    for j, c in enumerate(list(input().strip())):
      if c == '#':
        grids[i*w + j] = True
        dq.append((0, i, j))
  
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and not grids[(i+dx)*w + (j+dy)]:
        grids[(i+dx)*w + (j+dy)] = True
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

# def main():
#   h, w = map(int, input().split())
#   grids = [list(input().strip()) for _ in range(h)]
#   dq = deque()
#   for i in range(h):
#     for j in range(w):
#       if grids[i][j] == '#':
#         dq.append((0, i, j))
  
#   mcnt = -1
#   while dq:
#     cnt, i, j = dq.popleft()
#     for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
#       if 0 <= i+dx < h and 0 <= j+dy < w and grids[i+dx][j+dy] == '.':
#         grids[i+dx][j+dy] = '#'
#         dq.append((cnt+1, i+dx, j+dy))
#   print(cnt)
def main():
  h, w = map(int, input().split())
  grids = [list(map(lambda x: 1 if x=='#' else 0, input().strip())) for _ in range(h)]
  dq = deque()
  for i in range(h):
    for j in range(w):
      if grids[i][j] == 1:
        dq.append((0, i, j))
  
  mcnt = -1
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and grids[i+dx][j+dy] == 0:
        grids[i+dx][j+dy] = 1
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [list(input().strip()) for _ in range(h)]
  dq = deque()
  for i in range(h):
    for j in range(w):
      if grids[i][j] == '#':
        dq.append((0, i, j))
  
  mcnt = -1
  while dq:
    cnt, i, j = dq.popleft()
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and grids[i+dx][j+dy] == '.':
        grids[i+dx][j+dy] = '#'
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from queue import deque

def main():
  h, w = map(int, input().split())
  grids = [list(input().strip()) for _ in range(h)]
  dq = deque()
  for i in range(h):
    for j in range(w):
      if grids[i][j] == '#':
        dq.append((0, i, j))
  
  mcnt = -1
  while dq:
    cnt, i, j = dq.popleft()
    mcnt = cnt if cnt > mcnt else mcnt
    for dx, dy in zip([-1, 0, 1, 0], [0, -1, 0, 1]):
      if 0 <= i+dx < h and 0 <= j+dy < w and grids[i+dx][j+dy] == '.':
        grids[i+dx][j+dy] = '#'
        dq.append((cnt+1, i+dx, j+dy))
  print(cnt)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for y in range(H):
    for x, v in enumerate(input()):
        if v == '#':
            data.append([y, x, [], 0])

inf = H * W + 10
ans = [[inf for _ in range(W)] for __ in range(H)]

for v in data:
    ans[v[0]][v[1]] = 0

def check(destination, origin):
    return [destination[0], destination[1]] not in origin[2]

def cnt_update(ans, v):
    ans[v[0], v[1]] = v[3] + 1
"""
BFSまとめ
0. 現在位置、履歴、アクション数の3要素が必要
1. 更新する, アクション数を加算する
2. 条件を一致しているか、履歴に入っていないかを確認
3. popをループ
"""

fin = 0

while len(data):
    v = data.popleft()
    v[2].append([v[0], v[1]])

    if v[1] - 1 >= 0 and ans[v[0]][v[1] - 1] > v[3] + 1:
        v_left = [v[0], v[1] - 1, v[2], v[3] + 1]
        if check(v_left, v):
            ans[v_left[0]][v_left[1]] = v_left[3]
            data.append(v_left)
            if fin < v[3] + 1:
                fin = v[3] + 1

    if v[1] + 1 <= W - 1 and ans[v[0]][v[1] + 1] > v[3] + 1:
        v_right = [v[0], v[1] + 1, v[2], v[3] + 1]
        if check(v_right, v):
            ans[v_right[0]][v_right[1]] = v_right[3]
            data.append(v_right)
            if fin < v[3] + 1:
                fin = v[3] + 1

    if v[0] - 1 >= 0 and ans[v[0] - 1][v[1]] > v[3] + 1:
        v_up = [v[0] - 1, v[1], v[2], v[3] + 1]
        if check(v_up, v):
            ans[v_up[0]][v_up[1]] = v_up[3]
            data.append(v_up)
            if fin < v[3] + 1:
                fin = v[3] + 1

    if v[0] + 1 <= H - 1 and ans[v[0] + 1][v[1]] > v[3] + 1:
        v_down = [v[0] + 1, v[1], v[2], v[3] + 1]
        if check(v_down, v):
            ans[v_down[0]][v_down[1]] = v_down[3]
            data.append(v_down)
            if fin < v[3] + 1:
                fin = v[3] + 1

# print(max([a for aa in ans for a in aa]))
print(fin)

Submission status: Time Limit Exceeded

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

#A = [input() for _ in range(H)]

data = []

for y in range(H):
    for x, v in enumerate(input()):
        if v == '#':
            data.append([y, x, [], 0])

inf = H * W + 10
ans = [[inf for _ in range(W)] for __ in range(H)]

for v in data:
    ans[v[0]][v[1]] = 0

def check(destination, origin):
    return [destination[0], destination[1]] not in origin[2]

def cnt_update(ans, v):
    ans[v[0], v[1]] = v[3] + 1
"""
BFSまとめ
0. 現在位置、履歴、アクション数の3要素が必要
1. 更新する, アクション数を加算する
2. 条件を一致しているか、履歴に入っていないかを確認
3. popをループ
"""


while len(data):
    v = data.pop()
    v[2].append([v[0], v[1]])

    if v[1] - 1 >= 0 and ans[v[0]][v[1] - 1] > v[3] + 1:
        v_left = [v[0], v[1] - 1, v[2], v[3] + 1]
        if check(v_left, v):
            ans[v_left[0]][v_left[1]] = v_left[3]
            data.append(v_left)
    if v[1] + 1 <= W - 1 and ans[v[0]][v[1] + 1] > v[3] + 1:
        v_right = [v[0], v[1] + 1, v[2], v[3] + 1]
        if check(v_right, v):
            ans[v_right[0]][v_right[1]] = v_right[3]
            data.append(v_right)
    if v[0] - 1 >= 0 and ans[v[0] - 1][v[1]] > v[3] + 1:
        v_up = [v[0] - 1, v[1], v[2], v[3] + 1]
        if check(v_up, v):
            ans[v_up[0]][v_up[1]] = v_up[3]
            data.append(v_up)
    if v[0] + 1 <= H - 1 and ans[v[0] + 1][v[1]] > v[3] + 1:
        v_down = [v[0] + 1, v[1], v[2], v[3] + 1]
        if check(v_down, v):
            ans[v_down[0]][v_down[1]] = v_down[3]
            data.append(v_down)

print(max([a for aa in ans for a in aa]))