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())
a = []
for i in range(h):
    a.append(str(input()))
que = deque()
dist = [[-1]*w for i in range(h)]

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


dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
d = 0
while que:
    y, x = que.popleft() #幅優先探索
    d = dist[y][x]
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and dist[ny][nx] == -1:
            dist[ny][nx] = 0
            que.append((ny, nx))
            dist[ny][nx] = d + 1
print(d)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def main():
    h, w = list(map(int, input().split()))
    matrix = []
    for _ in range(h):
        matrix.append([c for c in input()])

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

    def step(q, m):
        next = []
        filled = deepcopy(m)
        while len(q) > 0:
            y, x = q.pop(0)

            for dy, dx in adj:
                if -1 < y + dy < h and -1 < x + dx < w:
                    if m[y + dy][x + dx] == '.':
                        filled[y + dy][x + dx] = '#'
                        next.append((y + dy, x + dx))

        return next, filled

    iq = []
    for i in range(h):
        for j in range(w):
            if matrix[i][j] == '#':
                iq.append((i, j))

    count = 0
    m = matrix
    while len(iq) > 0:
        # finished = all([m[i][j] == '#' for i in range(h) for j in range(w)])
        next, m = step(iq, m)
        if len(next) > 0:
            count += 1
            iq = next

    print(count)


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# agc033/agc033_a
import re
import math
import fractions
from pprint import pprint


[H, W] = [int(x) for x in input().split()]
A = [[0 for col in range(W)] for row in range(H)]
B = set()

for i in range(H):
    input_str = input()
    for j in range(W):
        A[i][j] = int(input_str[j] == '#')
        if A[i][j]:
            B.add((i, j))


def main(H, W, A, B):
    n = 0
    while True:
        C = set()
        for b in B:
            [i, j] = [b[0], b[1]]
            if i > 0 and not A[i-1][j]:
                A[i-1][j] = 1
                C.add((i-1, j))
            if i < H - 1 and not A[i+1][j]:
                A[i+1][j] = 1
                C.add((i+1, j))
            if j > 0 and not A[i][j-1]:
                A[i][j-1] = 1
                C.add((i, j-1))
            if j < W - 1 and not A[i][j+1]:
                A[i][j+1] = 1
                C.add((i, j+1))
        if C:
            B = C
            n += 1
        else:
            break
    print(str(n))


main(H, W, A, B)

Submission status: Time Limit Exceeded

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

Q = []
checked = set()
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            Q.append((i, j, 0))
            checked.add((i, j))

rest = H*W
it = 0

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

while rest > 0:
    rest -= 1
    x, y = Q[it][0:2]
    for i in range(4):
        if (x+dx[i], y+dy[i]) in checked or x + dx[i] < 0 or x + dx[i] >= H or y + dy[i] < 0 or y + dy[i] >= W:
            continue
        checked.add((x+dx[i], y+dy[i]))
        Q.append((x+dx[i], y+dy[i], Q[it][2]+1))
        ans = Q[it][2]+1
    it += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


H, W = map(int, input().split())
black_cells = []
for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == '#':
            black_cells.append(h*W+w)
def r(p):
    q_list = []
    h = p // W
    w = p % W
    if h != 0:
        q_list.append(p-W)
    if h != H-1:
        q_list.append(p+W)
    if w != 0:
        q_list.append(p-1)
    if w != W-1:
        q_list.append(p+1)
    return q_list


queue = deque(black_cells)
d = [10000]*H*W
for i in black_cells:
    d[i] = 0
while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p]+1:
            d[q] = d[p] + 1
            queue.append(q)
print(max(d))

Submission status: Time Limit Exceeded

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

queue = []
for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      queue.append([i, j])
queue.append([H, W])
cnt = 0

while len(queue) > 1:
  i, j = queue.pop(0)
  if i == H and j == W:
    queue.append([H, W])
    cnt += 1
    continue
  if i > 0 and A[i - 1][j] == ".":
    A[i - 1][j] = "#"
    queue.append([i - 1, j])
  if i < H - 1 and A[i + 1][j] == ".":
    A[i + 1][j] = "#"
    queue.append([i + 1, j])
  if j > 0 and A[i][j - 1] == ".":
    A[i][j - 1] = "#"
    queue.append([i, j - 1])
  if j < W - 1 and A[i][j + 1] == ".":
    A[i][j + 1] = "#"
    queue.append([i, j + 1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# import queue
from collections import deque

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

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = deque()

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.appendleft((i, j))

cnt = 0
while True:
    waiting = []
    while len(q) > 0:
        i, j = q.pop()
        if grid[i + 1][j] is False:
            grid[i + 1][j] = True
            waiting.append((i + 1, j))
        if grid[i - 1][j] is False:
            grid[i - 1][j] = True
            waiting.append((i - 1, j))
        if grid[i][j + 1] is False:
            grid[i][j + 1] = True
            waiting.append((i, j + 1))
        if grid[i][j - 1] is False:
            grid[i][j - 1] = True
            waiting.append((i, j - 1))

    if not waiting:
        break
    cnt += 1
    q.extendleft(waiting)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

if __name__=='__main__':
  # input
  H,W = map(int, input().split())
  A = [[' ' for i in range(W+2)] for j in range(H+2)]
  Q = []
  for i in range(H):
    input_list = input()
    for j in range(W):
      A[i+1][j+1]= input_list[j]
      if input_list[j]=='#':
        Q.append((i+1,j+1))
      
  # process
  for k in range(H+W):
    for q in Q[:]:
      l, m = q
      if A[l-1][m]=='.': Q.append((l-1,m))
      if A[l+1][m]=='.': Q.append((l+1,m))
      if A[l][m-1]=='.': Q.append((l,m-1))
      if A[l][m+1]=='.': Q.append((l,m+1))
      Q.pop(0)
    for q in Q[:]:
      l, m = q
      A[l][m] = '#'
    if len(Q) == 0:
      print(k)
      break;

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def atcoder_input():
    H, W = (int(i) for i in input().split())

    Q = deque()

    for h in range(H):
        l = [j for j in input().split()]

        for w in range(W):
            if list(l[0])[w] == "#":
                Q.append((h + 1, w + 1, 0))

    return Q, H, W


def main():
    Q, H, W = atcoder_input()
    searched = [[0] * (W + 2) for _ in range(H + 2)]

    for h in range(H + 2):
        searched[h][0] = 1
        searched[h][-1] = 1

    for w in range(W + 2):
        searched[0][w] = 1
        searched[-1][w] = 1

    max_count = 0

    while Q:
        h, w, count = Q.popleft()

        for (h2, w2) in ([h + 1, w], [h, w + 1], [h - 1, w], [h, w - 1]):
            if searched[h2][w2] == 1:
                continue
            else:
                searched[h2][w2] = 1

                if count + 1 > max_count:
                    max_count = count + 1
                Q.append((h2, w2, count + 1))

    print(max_count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))
que = deque()
allque = deque()

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

dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
d = 0
tmpque = deque()

while que:
    while que:
        y, x = que.popleft() #幅優先探索
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and (ny, nx) not in allque:
                tmpque.append((ny, nx))
                allque.append((ny, nx))
    que += tmpque
    allque = deque(set(allque))
    que = deque(set(que))
    tmpque = deque()
    if que:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


H,W=map(int, raw_input().split())
A=[ list( sys.stdin.readline().strip())  for i in range(H) ]


D=[ (-1,0),(1,0),(0,1),(0,-1) ]
K=[ [ float("inf") for j in range(W) ] for i in range(H)  ]  #Kyori

def bfs(h,w):
	V=[ [ 0 for j in range(W) ] for i in range(H)  ]
	q=deque()
	V[h][w]=1
	K[h][w]=0
	q.append( (h,w) )
	while q:
		h, w=q.popleft()	# newh , neww
		for dx,dy in D:
			if 0<=h+dx<H and 0<=w+dy<W:
				if A[h+dx][w+dy]=="." and V[h+dx][w+dy]==0:
					V[h+dx][w+dy]=1
					K[h+dx][w+dy]=min( K[h+dx][w+dy], K[h][w]+1 )
					q.append( (h+dx,w+dy) )	


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


ans=0
for i in range(H):
	ans=max(ans , max(K[i]))

print ans

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = [[[j,i] for i,s in enumerate(input()) if s=='#'] for j in range(H)]
A = [A[i][j] for i in range(len(A)) for j in range(len(A[i])) if not i==[]]
d = 0
for i in range(H):
    for j in range(W):
        n = min([abs(i-p[0])+abs(j-p[1]) for p in A])
        if(d<n):
            d = n
print(d)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# agc033/agc033_a
import re
import math
import fractions
from pprint import pprint


[H, W] = [int(x) for x in input().split()]
A = [[0 for col in range(W)] for row in range(H)]
B = []

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


def main(H, W, A, B):
    n = 0
    while True:
        C = []
        for k in range(len(B)):
            [i, j] = B[k]
            if i > 0 and not A[i-1][j]:
                A[i-1][j] = 1
                C.append((i-1, j))
            if i < H - 1 and not A[i+1][j]:
                A[i+1][j] = 1
                C.append((i+1, j))
            if j > 0 and not A[i][j-1]:
                A[i][j-1] = 1
                C.append((i, j-1))
            if j < W - 1 and not A[i][j+1]:
                A[i][j+1] = 1
                C.append((i, j+1))
        if C:
            B = C
            n += 1
        else:
            break
    print(str(n))


main(H, W, A, B)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int, input().split())
a=[[i for i in input()] for j in range(h)]
q=[]
ans=-1
for i in range(h):
    for j in range(w):
        if(a[i][j]=="#"):
            q.append([i,j])
while len(q)>0:
    tl=deque(q)
    q.clear()
    for i in tl:
        y=i[0]
        x=i[1]
        if(y>0):
            if(a[y-1][x]=="."):
                a[y-1][x]="#"
                q.append([y-1,x])
        if(x>0):
            if(a[y][x-1]=="."):
                a[y][x-1]="#"
                q.append([y,x-1])
        if(y<h-1):
            if(a[y+1][x]=="."):
                a[y+1][x]="#"
                q.append([y+1,x])
        if(x<w-1):
            if(a[y][x+1]=="."):
                a[y][x+1]="#"
                q.append([y,x+1])
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])

while (length > 0):
    gray = []
       
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
    
    gray2 = list(map(list, set(map(tuple, gray))))
    
    for l in gray2:
        black.append(l)
        white.remove(l)
        A[l[0]][l[1]] = "#"
        
    cnt += 1
    length = len(white)
    
print(cnt)

Submission status: Time Limit Exceeded

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

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

dist = [[0]*(W+1) for i in range(H+1)]
for i in range(H):
    dist[i][W] = 1
for i in range(W):
    dist[H][i] = 1
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = []
push = que.append
for i in range(H):
    di = dist[i]
    Ai = A[i]
    for j in range(W):
        if Ai[j] == '#':
            di[j] = 1
            push((i, j))

d = 0
que1 = []
push1 = que1.append
while que:
    for dx, dy in dd:
        for y, x in que:
            nx = x + dx; ny = y + dy
            if dist[ny][nx]:
                continue
            dist[ny][nx] = 1
            push1((ny, nx))
    que.clear()
    que, que1 = que1, que
    push, push1 = push1, push
    d += 1
sys.stdout.write("%d\n" % (d-1))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque

H, W = map(int, input().split())
A = []
checked = []
black = []
for i in range(H):
    tmp = input()
    A.append(tmp)
    checked.append([tmp[j] == '#' for j in range(W)])
    black += [((i, j), 0) for j in range(W) if checked[-1][j]]
black = deque(black)
ans = 0
while black:
    (i, j), d = black.popleft()
    ans = max(ans, d)
    if i > 0 and not checked[i-1][j]:
        checked[i-1][j] = True
        black.append(((i-1, j), d+1))
    if i < H-1 and not checked[i+1][j]:
        checked[i+1][j] = True
        black.append(((i+1, j), d+1))
    if j > 0 and not checked[i][j-1]:
        checked[i][j-1] = True
        black.append(((i, j-1), d+1))
    if j < W-1 and not checked[i][j+1]:
        checked[i][j+1] = True
        black.append(((i, j+1), d+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

q = queue.Queue(maxsize=-1)
for b in black:
    q.put(b)

max_dist = 0
while not q.empty():
    item = q.get()

    if i < 0 or j < 0 or i > H - 1 or j > W - 1:
        continue
    if A[item[0]][item[1]] == '#':
        dist[item[0]][item[1]] = 0
    else:
        a = dist[item[0] - 1][item[1]] if item[0] > 0 else 1000000
        b = dist[item[0]][item[1] - 1] if item[1] > 0 else 1000000
        c = dist[item[0] + 1][item[1]] if item[0] < H - 1 else 1000000
        d = dist[item[0]][item[1] + 1] if item[1] < W - 1 else 1000000
        dist[item[0]][item[1]] = min(a, b, c, d) + 1
        if dist[item[0]][item[1]] > max_dist:
            max_dist = dist[item[0]][item[1]]

    if item[0] > 0 and dist[item[0]-1][item[1]] == 1000000: q.put([item[0] - 1,item[1]])
    if item[1] > 0 and dist[item[0]][item[1]-1] == 1000000: q.put([item[0], item[1] - 1])
    if item[0] < H - 1 and dist[item[0]+1][item[1]] == 1000000: q.put([item[0] + 1, item[1]])
    if item[1] < W - 1 and dist[item[0]][item[1]+1] == 1000000: q.put([item[0], item[1] + 1])

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

from collections import deque

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

dist = [[-1] * W for _ in range(H)]
dq = deque()

for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            dist[r][c] = 0
            dq.append((r, c))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if not in_range(nr, nc): continue
        if dist[nr][nc] != -1: continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import queue

def solve(H: int, W: int, black):
    Q = queue.Queue()
    marked = [[False] * W for h in range(H)]
    qlen = 0
    for h, w in black:
        Q.put((h, w))
        qlen += 1
        marked[h][w] = True
    
    count = 0
    while not Q.empty():
        flag = False
        for _ in range(qlen):
            h, w = Q.get()
            qlen -= 1
            for hh, ww in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
                if 0 <= hh <= H-1 and 0 <= ww <= W-1 and not marked[hh][ww]:
                    flag = True
                    Q.put((hh, ww))
                    qlen += 1
                    marked[hh][ww] = True
        if flag:
            count += 1
    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    black = []
    for h in range(H):
        line = next(tokens)
        for w, c in enumerate(line):
            if c == '#':
                black.append((h, w))
    solve(H, W, black)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

dist = [[0]*(W+1) for i in range(H+1)]
for i in range(H):
    dist[i][W] = 1
for i in range(W):
    dist[H][i] = 1
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = []
push = que.append
for i in range(H):
    di = dist[i]
    Ai = A[i]
    for j in range(W):
        if Ai[j] == '#':
            di[j] = 1
            push((i, j))

d = 0
que1 = []
while que:
    push = que1.append
    for y, x in que:
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if dist[ny][nx]:
                continue
            dist[ny][nx] = 1
            push((ny, nx))
    que.clear()
    que, que1 = que1, que
    d += 1
sys.stdout.write("%d\n" % (d-1))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import queue

def solve(H: int, W: int, black):
    Q = queue.Queue()
    marked = [[0] * W for h in range(H)]
    qlen = 0
    for h, w in black:
        Q.put((h, w))
        qlen += 1
        marked[h][w] = 1
    
    count = 0
    while not Q.empty():
        flag = False
        for _ in range(qlen):
            h, w = Q.get()
            qlen -= 1
            for hh, ww in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
                if 0 <= hh <= H-1 and 0 <= ww <= W-1 and marked[hh][ww] == 0:
                    flag = True
                    Q.put((hh, ww))
                    qlen += 1
                    marked[hh][ww] = 1
        if flag:
            count += 1
    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    black = []
    for h in range(H):
        line = next(tokens)
        for w, c in enumerate(line):
            if c == '#':
                black.append((h, w))
    solve(H, W, black)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            q.append((0, i, j))

while len(q):
    d, i, j = q.popleft()
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        continue
    dists[i][j] = d
    q.append((d+1, i-1, j))
    q.append((d+1, i+1, j))
    q.append((d+1, i, j-1))
    q.append((d+1, i, j+1))

ans = max(map(max, dists))
print(ans)
# very slow
# ans = max(sum(dists, []))
# print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())   
queue = []
cost = [[-1]*W for i in range(H)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j] == '#':
      queue.append([i,j])
      cost[i][j] = 0
while queue:
  i,j = queue.pop(0)
  if i+1 < H and cost[i+1][j] < 0:
    queue.append([i+1,j])
    cost[i+1][j] = cost[i][j] + 1
  if i-1 >= 0 and cost[i-1][j] < 0:
    queue.append([i-1,j])
    cost[i-1][j] = cost[i][j] + 1
  if j+1 < W and cost[i][j+1] < 0:
    queue.append([i,j+1])
    cost[i][j+1] = cost[i][j] + 1
  if j-1 >= 0 and cost[i][j-1] < 0:
    queue.append([i,j-1])
    cost[i][j-1] = cost[i][j] + 1
flat = []
for i in range(H):
  flat.extend(cost[i])
print(max(flat))

Submission status: Time Limit Exceeded

Solution code:
X = [int(i) for i in input().split()]
queue = [(i,j) for i in range(X[0]) for j,s in enumerate(input()) if s=="#"]
end = []
for n in range(0,100000):
    tmp = []
    for q in queue:
        i,j = q[0],q[1]
        up = max(0, i-1)
        down = min(i+1, X[0]-1)
        left = max(0, j-1)
        right = min(j+1, X[1]-1)
        tmp += [(up,j),(down,j),(i,left),(i,right)]
    end += queue
    end = list(set(end))
    queue = [t for t in set(tmp) if t not in end]
    if len(queue) == 0:
        break
print(n)

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

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

ans = 0
min_ans = 0
for i in range(h):
    for j in range(w):
        min_dis = 10000000
        if a[i][j] == ".":
            for (x, y) in black:
                min_dis = min(abs(x - i) + abs(y - j), min_dis)
                if min_dis <= min_ans:
                    break
            ans = max(ans, min_dis)
            if min_dis > min_ans:
                min_ans = min_dis

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = ['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
ans = 0
queue = []
while True:
    l = []
    for i in range(1,h+1):
        for j in range(1,w+1):
            if not [i,j] in queue and a[i][j]=='#':
                queue += [[i,j]]
                l += [[i,j]]
    if len(queue)==h*w:
        break
    ans += 1
    for l_ in l:
        a[l_[0]-1] = a[l_[0]-1][:l_[1]]+'#'+a[l_[0]-1][l_[1]+1:]
        a[l_[0]] = a[l_[0]][:l_[1]-1]+'###'+a[l_[0]][l_[1]+2:]
        a[l_[0]+1] = a[l_[0]+1][:l_[1]]+'#'+a[l_[0]+1][l_[1]+1:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dict = {}
fuchi = {}
for i in range(h):
    Ai = input()
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            dict[(i, j)] = 1
            fuchi[(i, j)] = 1

def add(poj):
    res = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if poj[0] == 0:
        res[0] = 0
    if poj[0] == h - 1:
        res[1] = 0
    if poj[1] == 0:
        res[2] = 0
    if poj[1] == w - 1:
        res[3] = 0
    return res

def check(poj):
    i, j = poj[0], poj[1]
    if (i + 1, j) in dict and (i  - 1, j) in dict and (i, j + 1) in dict and (i, j - 1) in dict:
        return True
    else:
        return False

c = 0

while(True):
    if len(dict) == h * w:
        print(c)
        break
    pojs = {}
    for poj in fuchi.keys():
        for item in add(poj):
            if item != 0:
                pojs[(poj[0] + item[0], poj[1] + item[1])] = 1
    fuchi = {}
    for poj in pojs:
        dict[poj] = 1
        fuchi[poj] = 1
    c += 1

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

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

ans = 0
min_ans = 0
for i in range(h):
    for j in range(w):
        min_dis = 10000000
        if a[i][j] == ".":
            for (x, y) in black:
                min_dis = min(abs(x - i) + abs(y - j), min_dis)
                if min_dis < min_ans:
                    break
            ans = max(ans, min_dis)
            if min_dis > min_ans:
                min_ans = min_dis

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

intRow, intCol = map(int, input().split())

aryBoard = []
for intIdx in range(intRow):
    aryBoard.append(list(input()))
#print(aryBoard)

totalTurn = 0
boolCheck = True
while boolCheck:
    boolCheck = False

    tmpBoard = copy.deepcopy(aryBoard)
    for idxI in range(intRow):
        #print(aryBoard[idxI])
        for idxJ in range(intCol):
            # マスが黒色の場合、上下左右の白を黒に変える
            if aryBoard[idxI][idxJ] == "#":
                # 左
                if idxJ > 0 and aryBoard[idxI][idxJ - 1] == ".":
                    tmpBoard[idxI][idxJ - 1] = "#"
                    boolCheck = True
                    #print(idxI, idxJ, idxI, idxJ - 1)
                # 右
                if idxJ < intCol - 1 and aryBoard[idxI][idxJ + 1] == ".":
                    tmpBoard[idxI][idxJ + 1] = "#"
                    boolCheck = True
                    #print(idxI, idxJ, idxI, idxJ + 1)
                # 上
                if idxI > 0 and aryBoard[idxI - 1][idxJ] == ".":
                    tmpBoard[idxI - 1][idxJ] = "#"
                    boolCheck = True
                    #print(idxI, idxJ, idxI - 1, idxJ)
                # 下
                if idxI < intRow - 1 and aryBoard[idxI + 1][idxJ] == ".":
                    tmpBoard[idxI + 1][idxJ] = "#"
                    boolCheck = True
                    #print(idxI, idxJ, idxI + 1, idxJ)

    if boolCheck:
        totalTurn += 1

    aryBoard = copy.deepcopy(tmpBoard)
    #print(aryBoard)

print(totalTurn)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

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

dist = np.full((H, W), -1, dtype='int8')
dq = deque()

for r in range(H):
    for c in range(W):
        if a[r][c] == '#':
            dist[r, c] = 0
            dq.append((r, c))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


dr_s = (0, 0, -1, 1)
dc_s = (-1, 1, 0, 0)

d = 0
while dq:
    r, c = dq.popleft()
    d = dist[r][c]
    for dr, dc in zip(dr_s, dc_s):
        nr = r + dr
        nc = c + dc
        if not in_range(nr, nc): continue
        if dist[nr][nc] != -1: continue
        dist[nr][nc] = d + 1
        dq.append((nr, nc))

print(d)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = [[1 if c == "#" else 0 for c in list(str(input()))] for i in range(h)]
a = np.array(a)
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == 1:
            black.append([i, j])
            a[i][j] = 1
        else:
            a[i][j] = 0

ans = 0
min_ans = 0
for i in range(h):
    for j in range(w):
        min_dis = 10000000
        if a[i][j] == 0:
            for (x, y) in black:
                min_dis = min(abs(x - i) + abs(y - j), min_dis)
                if min_dis < min_ans:
                    break
            ans = max(ans, min_dis)
            if min_dis > min_ans:
                min_ans = min_dis

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dist = [[-1]*W for i in range(H)]
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            dist[i][j] = 0
            que.append((i, j))

d = 0
while que:
    y, x = que.popleft()
    d = dist[y][x]
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if not 0 <= nx < W or not 0 <= ny < H or dist[ny][nx] != -1:
            continue
        dist[ny][nx] = d+1
        que.append((ny, nx))
print(d)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = ['#'*(w+2)]+['#'+input()+'#' for _ in range(h)]+['#'*(w+2)]
ans = 0
while True:
    l = []
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='#':
                l += [[i,j]]
    if len(l)==h*w:
        break
    ans += 1
    for l_ in l:
        a[l_[0]-1] = a[l_[0]-1][:l_[1]]+'#'+a[l_[0]-1][l_[1]+1:]
        a[l_[0]] = a[l_[0]][:l_[1]-1]+'###'+a[l_[0]][l_[1]+2:]
        a[l_[0]+1] = a[l_[0]+1][:l_[1]]+'#'+a[l_[0]+1][l_[1]+1:]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

q = deque()
H, W = map(int, input().split())
dists = [[-1] * W for _ in range(H)]
for i in range(H):
    for j, v in enumerate(input()):
        if v == "#":
            q.append((0, i, j))

while len(q):
    d, i, j = q.popleft()
    if not 0 <= i < H or not 0 <= j < W or dists[i][j] != -1:
        continue
    dists[i][j] = d
    q.append((d+1, i-1, j))
    q.append((d+1, i+1, j))
    q.append((d+1, i, j-1))
    q.append((d+1, i, j+1))

ans = max(sum(dists, []))
print(ans)