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 copy
from collections import deque


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


def make_new_map(p_map):

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

    n_map = copy.deepcopy(p_map)
    reached = [[False for _ in range(W)] for _ in range(H)]

    for sh in range(H):
        for sw in range(W):
            if (reached[sh][sw] is False) and (p_map[sh][sw] == '#'):
                # start bfs
                togo = deque()
                togo.append((sh, sw))
                reached[sh][sw] = True
                while len(togo):
                    h, w = togo[0][0], togo[0][1]
                    togo.popleft()
                    for d in range(4):
                        nh, nw = h + dy[d], w + dx[d]
                        if nh < 0 or nw < 0 or nh >= H or nw >= W:
                            continue
                        if n_map[nh][nw] == '.':
                            n_map[nh][nw] = '#'
                        if reached[nh][nw] is True:
                            continue
                        if p_map[nh][nw] == '.':
                            continue
                        togo.append((nh, nw))
                        reached[nh][nw] = True
    return n_map


count = 0
next_map = make_new_map(past_map)
while past_map != next_map:
    count += 1
    past_map = copy.deepcopy(next_map)
    next_map = make_new_map(past_map)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
AA = [input() for _ in range(h)]
q = deque()
used = set()
for i in range(h):
    for j in range(w):
        if AA[i][j] == '#':
            q.append((j, i, 0))
            used.add((j, i))

max_depth = 0
while q:
    x, y, d = q.popleft()
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx , ny = x + dx, y + dy
        if (nx, ny) in used or nx < 0 or nx >= w or ny < 0 or ny >= h or AA[ny][nx] == '#':
            continue
        if d + 1 > max_depth:
            max_depth = d + 1
        q.append((nx, ny, d + 1))
        used.add((nx, ny))

print(max_depth)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
AA = [input() for _ in range(h)]
q = deque()
used = set()
for i in range(h):
    for j in range(w):
        if AA[i][j] == '#':
            q.append((j, i, 0))
            used.add((j, i))

max_depth = 0
while q:
    x, y, d = q.popleft()
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx , ny = x + dx, y + dy
        if nx < 0 or nx >= w or ny < 0 or ny >= h or AA[ny][nx] == '#' or (nx, ny) in used:
            continue
        if d + 1 > max_depth:
            max_depth = d + 1
        q.append((nx, ny, d + 1))
        used.add((nx, ny))

print(max_depth)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
AA = [input() for _ in range(h)]
blacks = set(
    (j, i)
    for i in range(h)
    for j in range(w)
    if AA[i][j] == '#'
)

if h * w == len(blacks):
    print(0)
else:
    if len(blacks) < h * w / 2:
        print(
            max(
                min(abs(i - y) + abs(j - x) for x, y in blacks)
                for i in range(h)
                for j in range(w)
                if AA[i][j] != '#'
            )
        )
    else:
        whites = set(
            (j, i)
            for i in range(h)
            for j in range(w)
            if AA[i][j] == '.'
        )
        print(
            max(
                min(abs(i - y) + abs(j - x) for x, y in whites)
                for i in range(h)
                for j in range(w)
                if AA[i][j] == '#'
            )
        )

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
AA = [input() for _ in range(h)]
blacks = set(
    (j, i)
    for i in range(h)
    for j in range(w)
    if AA[i][j] == '#'
)

if h * w == len(blacks):
    print(0)
else:
    print(
        max(
            min(abs(i - y) + abs(j - x) for x, y in blacks)
            for i in range(h)
            for j in range(w)
            if AA[i][j] != '#'
        )
    )

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
AA = [input() for _ in range(h)]
blacks = set()
for i in range(h):
  for j in range(w):
    if AA[i][j] == '#':
      blacks.add((j, i))

print(max(min(abs(i - y) + abs(j - x) for x, y in blacks) for i in range(h) for j in range(w)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
m = [[0] * (W + 1) for _ in range(H + 1)]
todo = deque()
for h in range(H):
    for w, c in enumerate(input()):
        if c == ".":
            m[h][w] = -1
        else:
            todo.append((h, w))
ans = 0
while todo:
    h, w = todo.popleft()
    count = m[h][w] + 1
    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nh = h + dh
        nw = w + dw
        if m[nh][nw] == -1:
            m[nh][nw] = count
            todo.append((nh, nw))
            ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
m = [[-1 if c == "." else 0 for c in input() + "#"] for _ in range(H)]
m.append([0] * (W + 1))
todo = deque(((h, w) for h in range(H) for w in range(W) if m[h][w] == 0))
ans = 0
while todo:
    h, w = todo.popleft()
    count = m[h][w] + 1
    for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nh = h + dh
        nw = w + dw
        if m[nh][nw] == -1:
            m[nh][nw] = count
            todo.append((nh, nw))
            ans = count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
grid = [list(input().replace("#","0")) for i in range(n)]
ans = 0
cnt = 0
temp = 0
loc = []
move = [[0,-1],[0,1],[1,0],[-1,0]]
for i in range(n):
  grid[i] = ["/"] + grid[i] + ["/"]
  cnt += "".join(grid[i]).count(".")
  
grid.insert(0,["/"]*(m+2))
grid.append(["/"]*(m+2))

while cnt > 0:
  temp = 0
  loc = []
  for j in range(1,n+1):
    for k in range(1,m+1):  
      if grid[j][k] == str(ans):
        loc.append([j,k])
      
  for x,y in loc:
    for dx,dy in move:
      if grid[x+dx][y+dy] == "/" or grid[x+dx][y+dy].isnumeric():
        continue
      else:
        grid[x+dx][y+dy] = str(ans+1)

  for i in range(1,n+1):
    temp += "".join(grid[i]).count(".")
    cnt = temp
  ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = [int(x) for x in input().split()]
masu = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[-1] * W for i in range(H)]

def bfs():
    q = deque()
    for x in range(H):
        for y in range(W):
            if masu[x][y] == '#':
                q.append([x, y])
                d[x][y] = 0
    while q:
        x, y = q.popleft()
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and d[nx][ny] == -1:
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    ans = -1
    for x in range(H):
        for y in range(W):
            ans = max(ans, d[x][y])
    return ans

print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = [int(x) for x in input().split()]
masu = [input() for i in range(H)]
move = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = [[-1] * W for i in range(H)]

def bfs():
    q = deque()
    for x in range(H):
        for y in range(W):
            if masu[x][y] == '#':
                q.append([x, y])
                d[x][y] = 0
    while q:
        x, y = q.popleft()
        for v in move:
            nx = x + v[0]
            ny = y + v[1]
            if 0 <= nx < H and 0 <= ny < W and masu[nx][ny] == '.' and d[nx][ny] == -1:
                q.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    max = -1
    for x in range(H):
        for y in range(W):
            if d[x][y] > max:
                max = d[x][y]
    return max

print(bfs())

Submission status: Time Limit Exceeded

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



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()

que_count = 0
for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            que.append((h,w))
            que_count += 1
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
nq = 0
while cot != H*W:
    while que_count != 0 and cot != H*W:
        h,w = que.popleft()
        que_count -= 1

        for temp in go:
            # この時，実際に行くのかは不明
            gx,gy = temp
            nx = w + gx
            ny = h + gy

            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                # この時に実際に移動する
                gone[ny][nx] = 1
                que.append( (ny,nx))
                nq += 1
                cot += 1
    que_count = nq
    nq = 0
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = [[0] * W for _ in range(H)]
cot = 0
que = deque()
next_que =  deque()

for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            next_que.append((h,w))
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
que = next_que
while cot != H*W:
    que = copy.deepcopy(next_que)
    next_que = deque()
    while que:
        h,w = que.popleft()
        for temp in go:
            gx,gy = temp
            nx = w + gx
            ny = h + gy
            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                gone[ny][nx] = 1
                next_que.append( (ny,nx))
                cot += 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
from collections import defaultdict
import copy
import numpy as np
# input = sys.stdin.readline



H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
gone = np.zeros((H,W))
cot = 0
que = deque()
next_que =  deque()

for h in range(H):
    for w in range(W):
        if C[h][w] == "#":
            gone[h][w] = 1
            next_que.append((h,w))
            cot += 1
INF = 10 ** 9
go = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans  = 0
que = next_que
while cot != H*W:
    que = copy.deepcopy(next_que)
    next_que = deque()
    while que:
        h,w = que.popleft()
        for temp in go:
            gx,gy = temp
            nx = w + gx
            ny = h + gy
            if 0<= nx < W and 0<= ny < H and gone[ny][nx] != 1: #行って無かったら，行く
                gone[ny][nx] = 1
                next_que.append( (ny,nx))
                cot += 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
d = [[-1]*W for i in range(H)]
#temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]

black_cells = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            black_cells.append((i,j))
            d[i][j] = 0

def bfs():
    #max = 0
    #dx = [1, 0, -1, 0]
    #dy = [0, 1, 0, -1]

    #que = deque([])
    s = 0
    while black_cells:
        p, q = black_cells.popleft()
        s = d[p][q]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx = q + dx
            ny = p + dy
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and d[ny][nx]==-1:
                #que.append((nx))
                #temp[ny][nx] = d[p[0]][p[1]] + 1
                #a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                #if a < d[ny][nx]:
                black_cells.append((ny, nx))
                d[ny][nx] = s + 1
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return s






#for i in slist:
#    s = bfs(i[0], i[1])

print(bfs())
#print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
d = [[-1]*W for i in range(H)]
#temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]

black_cells = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            black_cells.append((i,j))
            d[i][j] = 0

def bfs():
    #max = 0
    #dx = [1, 0, -1, 0]
    #dy = [0, 1, 0, -1]

    #que = deque([])
    s = 0
    while black_cells:
        p = black_cells.popleft()
        s = d[p[0]][p[1]]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            nx = p[1] + dx
            ny = p[0] + dy
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and d[ny][nx]==-1:
                #que.append((nx))
                #temp[ny][nx] = d[p[0]][p[1]] + 1
                #a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                #if a < d[ny][nx]:
                black_cells.append((ny, nx))
                d[ny][nx] = s + 1
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return s






#for i in slist:
#    s = bfs(i[0], i[1])

print(bfs())
#print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
d = [[-1]*W for i in range(H)]
#temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]

black_cells = deque()
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            black_cells.append((i,j))
            d[i][j] = 0

def bfs():
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    #que = deque([])
    s = 0
    while black_cells:
        p = black_cells.popleft()
        s = d[p[0]][p[1]]
        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and d[ny][nx]==-1:
                #que.append((nx))
                #temp[ny][nx] = d[p[0]][p[1]] + 1
                #a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                #if a < d[ny][nx]:
                black_cells.append((ny, nx))
                d[ny][nx] = s + 1
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return s






#for i in slist:
#    s = bfs(i[0], i[1])

print(bfs())
#print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

def bfs():
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    for i in slist:
        que.append((i[0], i[1]))
        d[i[0]][i[1]] = 0


    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if a < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = a
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]

slist = []
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            slist.append((i,j))



#for i in slist:
#    s = bfs(i[0], i[1])

print(bfs())
#print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

def bfs(sy, sx):
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]
            #a = temp[ny][nx]
            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                a = temp[ny][nx]
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if a < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = a
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]
maze = [list(input()) for i in range(H)]
slist = []
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            slist.append((i, j))

for i in slist:
    s = bfs(i[0], i[1])

print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

global d
global temp

def bfs(sy, sx):
    #max = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

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

            if 0<=nx<W and 0<=ny<H and maze[ny][nx]!="#":
                #que.append((nx))
                temp[ny][nx] = d[p[0]][p[1]] + 1
                #d[ny][nx] = d[p[0]][p[1]] + 1
                if temp[ny][nx] < d[ny][nx]:
                    que.append((ny, nx))
                    d[ny][nx] = temp[ny][nx]
                    #if max < d[ny][nx]:
                        #max = d[ny][nx]

    return np.max(np.array(d))

H, W = map(int, input().split())
d = [[float("inf")]*W for i in range(H)]
temp = [[float("inf")]*W for i in range(H)]

maze = [list(input()) for i in range(H)]
slist = []
for i in range(H):
    for j in range(W):
        if maze[i][j]=="#":
            slist.append((i, j))

for i in slist:
    #s = bfs(i[0], i[1])
    #if s>max:
       # max = s
    s = bfs(i[0], i[1])

print(s)

Submission status: Time Limit Exceeded

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

A = [['#' for i in range(W + 2)]]\
    + [list('#' + input() + '#') for i in range(H)]\
    + [['#' for i in range(W + 2)]]

import collections
q = collections.deque()
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if A[i][j] == '#':
            q.appendleft((i, j, 0))

while True:
    i, j, c = q.pop()
    if A[i - 1][j] == '.':
        q.appendleft((i - 1, j, c + 1))
        A[i - 1][j] = '#'
    if A[i + 1][j] == '.':
        q.appendleft((i + 1, j, c + 1))
        A[i + 1][j] = '#'
    if A[i][j - 1] == '.':
        q.appendleft((i, j - 1, c + 1))
        A[i][j - 1] = '#'
    if A[i][j + 1] == '.':
        q.appendleft((i, j + 1, c + 1))
        A[i][j + 1] = '#'


    if len(q) == 0:
        print(c)
        break

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

H, W = imn()
count = [[-1 for _ in range(W)] for _ in range(H)]
queue = deque([])
A = []
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#': 
            queue.append((i,j))
            count[i][j] = 0
    A.append(list(s))

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
ans = 0
while len(queue) > 0:
    point = queue.popleft()
    for i in range(4):
        x = point[1] + dx[i]
        y = point[0] + dy[i]
        if x < 0 or x >= W or y < 0 or y >= H: continue
        if count[y][x] != -1: continue
        count[y][x] = count[point[0]][point[1]] + 1
        queue.append((y,x))
        ans = max(ans, count[y][x])
print(ans)

Submission status: Time Limit Exceeded

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

from collections import deque
def solve():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    ans=0
    while True:
        Q = deque()
        cnt=0
        for y in range(h):
            for x in range(w):
                if l[y][x] == "#":
                    Q.append([x,y])
                    cnt+=1
        if cnt >= h*w:
            return ans

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

                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]==".":
                        l[ny][nx] = "#"

print(solve())

Submission status: Time Limit Exceeded

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

def readlines(n):
    for h in range(n):
        yield {(h, w) for w, p in enumerate(input().rstrip()) if p == "#"}

def main():
    H, W = map(int, input().split())
    s = set()
    for lines in readlines(H):
        s |= lines

    dires = [(-1,0),(0, 1),(1, 0),(0, -1)]
    q = deque(s)

    ans = 0
    next_q = set()
    while q:
        h, w = q.popleft()
        for y, x in dires:
            suc_y = h+y
            suc_x = w+x
            if suc_x < 0 or suc_y < 0 or suc_x >= W or suc_y >= H or (suc_y,suc_x) in s:
                continue
            s.add((suc_y,suc_x))
            next_q.add((suc_y, suc_x))

        if not q:
            ans += 1
            q = deque(next_q)
            next_q = set()
    print(ans-1)


main()

Submission status: Time Limit Exceeded

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

def readlines(n):
    for h in range(n):
        yield [(h, w) for w, p in enumerate(input().rstrip()) if p == "#"]

def main():
    H, W = map(int, input().split())
    s = set()
    for lines in readlines(H):
        s.update(lines)

    dires = [(-1,0),(0, 1),(1, 0),(0, -1)]
    q = deque(s)

    ans = 0
    next_q = set()
    while q:
        h, w = q.popleft()
        for y, x in dires:
            suc_y = h+y
            suc_x = w+x
            if suc_x < 0 or suc_y < 0 or suc_x >= W or suc_y >= H or (suc_y,suc_x) in s:
                continue
            s.add((suc_y,suc_x))
            next_q.add((suc_y, suc_x))

        if not q:
            ans += 1
            q = deque(next_q)
            next_q = set()
    print(ans-1)


main()

Submission status: Time Limit Exceeded

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

def readlines(n):
    for _ in range(n):
        yield list(input().rstrip())

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

    dires = [(-1,0),(0, 1),(1, 0),(0, -1)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j))
    ans = 0
    next_q = set()
    while q:
        h, w = q.popleft()
        for y, x in dires:
            suc_y = h+y
            suc_x = w+x
            if suc_x < 0 or suc_y < 0 or suc_x >= W or suc_y >= H or A[suc_y][suc_x] == "#":
                continue
            A[suc_y][suc_x] = "#"
            next_q.add((suc_y, suc_x))

        if not q:
            ans += 1
            q = deque(next_q)
            next_q = set()
    print(ans-1)


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def readlines(n):
    for _ in range(n):
        yield list(input())

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

    dires = [(-1,0),(0, 1),(1, 0),(0, -1)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j))
    next_q = set()
    ans = 0
    while q:
        h, w = q.popleft()
        for y, x in dires:
            suc_y = h+y
            suc_x = w+x
            if suc_x < 0 or suc_y < 0 or suc_x >= W or suc_y >= H or A[suc_y][suc_x] == "#":
                continue
            A[suc_y][suc_x] = "#"
            next_q.add((suc_y, suc_x))

        if not q:
            ans += 1
            q = deque(next_q)
            next_q = set()

    print(ans-1)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

d = [[ sys.maxsize for b in range(W)] for a in range(H)]

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

q = deque()

for y in range(H):
  for x in range(W):
    if c[y][x] == '#':
      q.append([y, x])
      d[y][x] = 0
ans = 0
while len(q) > 0:
  y, x = q.popleft()
  for i in range(4):
    ny = y + dy[i]
    nx = x + dx[i]
    if 0 <= nx and nx <= W-1 and 0 <= ny and ny <= H-1 and c[ny][nx] == '.' and d[ny][nx] == sys.maxsize:
      q.append([ny, nx])
      d[ny][nx] = d[y][x]+1
      ans = max(ans, d[ny][nx])

      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# BFS
from collections import deque
import numpy as np


def main():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    # 頂点数と辺数
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    # 全頂点を未訪問に初期化
    dist = [[-1] * W for _ in range(H)]

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

    # bfs開始 (キューが空になるまで探索を行う)
    while len(que) > 0:
        v = que.popleft()  # キューから先頭頂点を取り出す
        for i in range(4):
            nx = v[0] + dx[i]
            ny = v[1] + dy[i]
            if (0 <= nx and nx < H and 0 <= ny and ny < W and dist[nx][ny] == -1):
                que.append([nx, ny])
                dist[nx][ny] = dist[v[0]][v[1]] + 1
    print(np.max(dist))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# BFS
from collections import deque
import numpy as np
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
# 頂点数と辺数
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
# 全頂点を未訪問に初期化
dist = [[-1] * W for _ in range(H)]

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

# bfs開始 (キューが空になるまで探索を行う)
while len(que) > 0:
    v = que.popleft()  # キューから先頭頂点を取り出す
    for i in range(4):
        nx = v[0] + dx[i]
        ny = v[1] + dy[i]
        if (0 <= nx and nx < H and 0 <= ny and ny < W and A[nx][ny] != '#' and dist[nx][ny] == -1):
            que.append([nx, ny])
            dist[nx][ny] = dist[v[0]][v[1]] + 1
print(np.max(dist))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

h, w = map(int, input().split())
# 蛮兵
painted = [['#'] * (w + 2)]
painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
painted.append(['#'] * (w + 2))
que = []

for y in range(1, h + 1):
    for x in range(1, w + 1):
        if painted[y][x] == '#':
            painted[y][x] = 0
            que.append((y, x))
cnt = 0
while que:
    qq = []
    for y, x in que:
        if painted[y - 1][x] == '.':
            painted[y - 1][x] = painted[y][x] + 1
            qq.append((y - 1, x))
        if painted[y + 1][x] == '.':
            painted[y + 1][x] = painted[y][x] + 1
            qq.append((y + 1, x))
        if painted[y][x + 1] == '.':
            painted[y][x + 1] = painted[y][x] + 1
            qq.append((y, x + 1))
        if painted[y][x - 1] == '.':
            painted[y][x - 1] = painted[y][x] + 1
            qq.append((y, x - 1))
    que = qq

print(painted[y][x])