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:
h,w=map(int,input().split())
li=[input() for i in range(h)]
black=[]




for i in range(h):
    for j  in range(w):
        if li[i][j]=="#":
            black.append([i,j])
            
def check(li,i,j,black,count):
    v=[]
    for k in black:
        if abs(k[0]-i)+abs(k[1]-j)<=count:
            return(0)
        else:
            v.append(abs(k[0]-i)+abs(k[1]-j))
 #   print(min(v))
    return min(v)
    
        
        
    

count=0

for i in range(h):
    for j  in range(w):
        if li[i][j]==".":
            count=max(count,check(li,i,j,black,count))
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

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

    ret = 0
    visited = [False] * (W * H)
    while 0 < len(queue) and 0 < rem:
        i, j, n = queue.popleft()
        k = i * W + j
        if visited[k]:
            continue
        visited[k] = True
        ret = n
        rem -= 1

        if 0 < j and not visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if j < (W - 1) and not visited[k + 1]:
            queue.append((i, j + 1, n + 1))
        if 0 < i and not visited[k - W]:
            queue.append((i - 1, j, n + 1))
        if i < (H - 1) and not visited[k + W]:
            queue.append((i + 1, j, n + 1))
    return ret


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
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

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 = []
# WAで時間計測
for n in range(0,100):
    tmp = []
    end += queue
    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 += [t for t in [(up,j),(down,j),(i,left),(i,right)] if t not in end]
    queue = list(set(tmp))
    if len(queue) == 0:
        break
print(n)

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 = []
    end += queue
    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 += [t for t in [(up,j),(down,j),(i,left),(i,right)] if t not in end]
    queue = list(set(tmp))
    if len(queue) == 0:
        break
print(n)

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 = []

cnt = 0

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

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

Submission status: Time Limit Exceeded

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

inf = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    dist = [[inf] * W for h in range(H)]
    for h in range(H):
        for w in range(W):
            hh = max(h-1, 0)
            ww = max(w-1, 0)            
            if A[h][w] == '#':
                dist[h][w] = 0
            else:
                dist[h][w] = min(dist[hh][w], dist[h][ww]) + 1
    
    dmax = 0
    for h in range(H-1, -1, -1):
        for w in range(W-1, -1, -1):
            hh = min(h+1, H-1)
            ww = min(w+1, W-1)
            dist[h][w] = min(dist[h][w], dist[h][ww] + 1, dist[hh][w] + 1)
            dmax = max(dist[h][w], dmax)
    print(dmax) 
    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
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue as qu


words = lambda t : list(map(t, input().split()))

h,w = words(int)
mat = []
for _ in range(h):
    a = list(input())
    mat.append(a)

#print(mat)

q = qu.Queue()
for i in range(h):
    for j in range(w):
        if mat[i][j] == "#":
            q.put((i,j))

prev = q
round = -1
while not prev.empty():
    round += 1
    next = qu.Queue()
    while not prev.empty():
        (x,y) = prev.get()
        if x != 0 and mat[x-1][y] != "#":
            next.put((x-1,y))
            mat[x-1][y] = "#"
        if y != 0 and mat[x][y-1] != "#":
            next.put((x,y-1))
            mat[x][y-1] = "#"
        if x != h-1 and mat[x+1][y] != "#":
            next.put((x+1,y))
            mat[x+1][y] = "#"
        if y != w-1 and mat[x][y+1] != "#":
            next.put((x,y+1))
            mat[x][y+1] = "#"
    prev = next

print(round)

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W, *A = sys.stdin.read().split()
H = int(H); W = int(W)

INF = 8000
dist = [[INF]*(W) for i in range(H)]
for i in range(H):
    di = dist[i]
    Ai = A[i]
    for j, a in enumerate(Ai):
        if a == '#':
            di[j] = 0
for i in range(H):
    cur = INF
    di = dist[i]
    for j in range(W):
        if di[j] == 0:
            cur = 0
        else:
            di[j] = cur = cur+1
    cur = INF
    for j in range(W-1, -1, -1):
        if di[j] == 0:
            cur = 0
        else:
            di[j] = cur = min(di[j], cur+1)
for j in range(W):
    cur = INF
    for di in dist:
        if cur+1 < di[j]:
            di[j] = cur = cur+1
        else:
            cur = di[j]
    cur = INF
    for di in reversed(dist):
        if cur+1 < di[j]:
            di[j] = cur = cur+1
        else:
            cur = di[j]
sys.stdout.write("%d\n" % max(max(di) for di in dist))

Submission status: Time Limit Exceeded

Solution code:
# import queue
# from collections import deque

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

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

# q = deque()
q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] == 1:
            q.append((i, j))

cnt = 0
while True:
    qq = []
    for (i, j) in q:
        # i, j = q.pop()
        if grid[i + 1][j] == 0:
            grid[i + 1][j] = 1
            qq.append((i + 1, j))
        if grid[i - 1][j] == 0:
            grid[i - 1][j] = 1
            qq.append((i - 1, j))
        if grid[i][j + 1] == 0:
            grid[i][j + 1] = 1
            qq.append((i, j + 1))
        if grid[i][j - 1] == 0:
            grid[i][j - 1] = 1
            qq.append((i, j - 1))

    if not qq:
        break
    cnt += 1
    q = qq

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from collections import deque

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

Submission status: Time Limit Exceeded

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

queue = []
for i in range(H):
  A.append(list(input()))
  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:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

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

    ret = 0
    visited = [False] * (W * H)
    while 0 < len(queue) and 0 < rem:
        i, j, n = queue.popleft()
        if visited[i * W + j]:
            continue
        visited[i * W + j] = True
        #ret = max(ret, n)
        ret = n
        rem -= 1

        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < W - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < H - 1:
            queue.append((i + 1, j, n + 1))
    return ret


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
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
inputs = raw_input().replace("\n", "").split(" ")
H, W = map(int, inputs)

m = [ [-1 for x in range(W)] for y in range(H)]

count = 0
zero_coords = []
for y in range(H):
    #line = list(input())
    line = list(raw_input().replace("\n", ""))
    for x, point in enumerate(line):
        if point == "#":
            m[y][x] = 0
            zero_coords.append([y, x])
            count += 1

tmp_coords = zero_coords
#mawari_soutais = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
mawari_soutais = [[-1, 0], [0, -1], [0, 1], [1, 0]]

val = 0
while count < H*W:
    val += 1
    new_tmp_coords = []
    for center_coord in tmp_coords:
        for mawari_soutai in mawari_soutais:
            mawari_coord = [mawari_soutai[i] + center_coord[i] for i in range(2)]
            y, x = mawari_coord
            if y < 0 or H <= y or x < 0 or W <= x or m[y][x] != -1:
                continue
            else:
                m[y][x] = val
                count += 1
                new_tmp_coords.append([y, x])
    tmp_coords = new_tmp_coords
    #print(m)

out = val
print(out)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x,y=map(lambda x,y: x+y, cur, direction)
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
        ans=max(ans, max(memo[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# input
h, w = [int(i) for i in input().split()]
ary = []
for y in range(h):
    ary.append([None if i == '.' else 0 for i in input()])


update_list = set((y, x) for y, line in enumerate(ary) for x, elem in enumerate(line) if elem == 0)

from copy import copy
def update(ary, update_list):
    for pos in copy(update_list):
        y, x = pos
        if x > 0:
            uy, ux = y, x-1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_list.add((uy, ux))
        if x < w-1:
            uy, ux = y, x+1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_list.add((uy, ux))
        if y > 0:
            uy, ux = y-1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_list.add((uy, ux))
        if y < h-1:
            uy, ux = y+1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_list.add((uy, ux))
        update_list.remove((y, x))
    return ary, update_list


black_count = len(update_list)
while black_count < w * h:
    ary, update_list = update(ary, update_list)
    black_count += len(update_list)


print(max(elem for line in ary for elem in line))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = deque()
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            b.append([h, w, 0])

ans = 0
while len(b) > 0:
    h, w, d = b.popleft()
    for y, x in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = h + y, w + x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == '.':
            b.append([nh, nw, d + 1])
            ans = max([ans, d + 1])
            hw[nh][nw] = "#"
print(ans)

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()
q = []

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

cnt = 0
while True:
    qq = []
    for (i, j) in q:
        # i, j = q.pop()
        if grid[i + 1][j] is False:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if grid[i - 1][j] is False:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if grid[i][j + 1] is False:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if grid[i][j - 1] is False:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    if not qq:
        break
    cnt += 1
    q = qq

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = []
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            b.append([h, w, 0])

ans = 0
while len(b) > 0:
    h, w, d = b.pop(0)
    for y, x in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = h + y, w + x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == '.':
            b.append([nh, nw, d + 1])
            ans = max([ans, d + 1])
            hw[nh][nw] = "#"
print(ans)

Submission status: Time Limit Exceeded

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

A=[]
for i in range(H):
    A.append(list(input()))

table=[]
for i in range(H):
    row=[]
    for j in range(W):
        if A[i][j]=="#":
            row.append(0)
        else:
            row.append(H+W)
    table.append(row)

def change(table1,ii):
    for i in range(H):
        for j in range(W):
             if table1[i][j]==ii:
                if j+1<W:
                    table1[i][j+1]=min(ii+1,table[i][j+1])
                if j-1>=0:
                    table1[i][j-1]=min(ii+1,table[i][j-1])
                if i+1<H:
                    table1[i+1][j]=min(ii+1,table[i+1][j])
                if i-1>=0:
                    table1[i-1][j]=min(ii+1,table[i-1][j])
    return(table1)

for i in range(H+W):
    table=change(table,i)
ans=[]
for x in table:
    ans.append(max(x))
ans=max(ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

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

    ret = 0
    visited = [[False] * W for _ in range(H)]
    while 0 < len(queue):
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)
        rem -= 1
        if rem == 0:
            break

        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < W - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < H - 1:
            queue.append((i + 1, j, n + 1))
    return ret


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
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def d(i, j, x, y):
    return abs(x - j) + abs(y - i)

s = []

a = list(map(int, input().split()))
for i in range(a[0]):
    b = input()
    for j in range(a[1]):
        if b[j] == '#':
            s.append([i, j])

d_max = 0
diag = d(0, 0, a[1], a[0])

for i in range(a[0]):
    for j in range(a[1]):
        if [i, j] not in s:
            d_min = diag
            for p in s:
                dist = d(i, j, p[1], p[0])
                if dist <= d_max:
                    d_min = dist
                    break
                else:
                    d_min = min(d_min, dist)
            d_max = max(d_max, d_min)

print(d_max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import chain
H, W = map(int, input().split())
G = chain.from_iterable([[s == '#' for s in input()] for _ in range(H)])
dist = [0]*(H*W)
B = deque([i for i, g in enumerate(G) if g])
visited = set(B)
while B:
    vij = B.pop()
    for dij in (W, -W, 1, -1):
        nij = vij + dij
        if (dij == 1 and not nij % W) or (dij == -1 and not (nij+1) % W) or not (0 <= nij < H*W) or nij in visited:
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[vij]
        B.appendleft(nij)
print(max(dist))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
H, W = 0, 0
A = []


def set_inputs():
    global H, W, A
    H, W = get_li()
    A = [get_str() for _ in range(H)]
    return


def main():
    set_inputs()
    # ----------MAIN----------
    stage = [[0 for _ in range(W)] for _ in range(H)]
    remaining = deque()
    for i, ai_ in enumerate(A):
        for j, a in enumerate(ai_):
            if a == ".":
                continue
            stage[i][j] = 1
            remaining.append((i, j))
    ans = 0
    while remaining:
        _next = deque()
        for (i, j) in remaining:
            stage[i][j] = 2
            if i > 0 and stage[i-1][j] == 0:
                stage[i-1][j] = 1
                _next.append((i-1, j))
            if i < H - 1 and stage[i+1][j] == 0:
                stage[i+1][j] = 1
                _next.append((i+1, j))
            if j > 0 and stage[i][j-1] == 0:
                stage[i][j-1] = 1
                _next.append((i, j-1))
            if j < W - 1 and stage[i][j+1] == 0:
                stage[i][j+1] = 1
                _next.append((i, j+1))
        remaining = _next
        ans += 1
    print(max(ans - 1, 0))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve(H: int, W: int, A: "List[str]"):
    Q = queue.Queue()
    marked = [[False for w in range(W)] for h in range(H)]
    qlen = 0
    for h, line in enumerate(A):
        for w, c in enumerate(line):
            if c == '#':
                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 hh < 0 or hh >= H or ww < 0 or ww >= W:
                    continue
                if marked[hh][ww]:
                    continue
                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
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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 = 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:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while 0 < len(queue):
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)

        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < W - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < H - 1:
            queue.append((i + 1, j, n + 1))
    return ret


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
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

m = [ [-1 for x in range(W)] for y in range(H)]

count = 0
zero_coords = []
for y in range(H):
    line = list(input())
    for x, point in enumerate(line):
        if point == "#":
            m[y][x] = 0
            zero_coords.append([y, x])
            count += 1

tmp_coords = zero_coords
#mawari_soutais = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
mawari_soutais = [[-1, 0], [0, -1], [0, 1], [1, 0]]

val = 0
while count < H*W:
    val += 1
    new_tmp_coords = []
    for center_coord in tmp_coords:
        for mawari_soutai in mawari_soutais:
            mawari_coord = [mawari_soutai[i] + center_coord[i] for i in range(2)]
            y, x = mawari_coord
            if y < 0 or H <= y or x < 0 or W <= x or m[y][x] != -1:
                continue
            else:
                m[y][x] = val
                count += 1
                new_tmp_coords.append([y, x])
    tmp_coords = new_tmp_coords
    #print(m)

out = val
print(out)

Submission status: Time Limit Exceeded

Solution code:
h,w = [int(i) for i in input().split()]
x = []
for i in range(h):
    x.append(input())

search = []
board = {}
for i in range(h):
    for j in range(w):
        if x[i][j] == "#":
            board[(i,j)] = 0
            search.append((i,j))

count = 1
ans = 0
while search:
    search2 = []
    for xy in search:
        x,y = xy
        if (x+1,y) not in board and x+1 <h:
            board[(x+1,y)] = count
            search2.append((x+1,y))
            ans = count
        if (x-1,y) not in board and x-1 >=0:
            board[(x-1,y)] = count
            search2.append(((x-1,y)))
            ans = count
        if (x,y+1) not in board and y+1 <w:
            board[(x,y+1)] = count
            search2.append((x,y+1))
            ans = count
        if (x,y-1) not in board and y-1 >=0:
            board[(x,y-1)] = count
            search2.append((x,y-1))
            ans = count
    search = search2
    count +=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W, *A = sys.stdin.read().split()
H = int(H); W = int(W)

INF = 8000
dist = [[INF]*(W+1) for i in range(H+1)]
dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
que = []
for i in range(H):
    di = dist[i]
    Ai = A[i]
    for j, a in enumerate(Ai):
        if a == '#':
            di[j] = 0
for i in range(H):
    cur = INF
    di = dist[i]
    for j in range(W):
        di[j] = cur = min(cur+1, di[j])
    cur = INF
    for j in range(W-1, -1, -1):
        di[j] = cur = min(cur+1, di[j])
for j in range(W):
    cur = INF
    for i in range(H):
        dist[i][j] = cur = min(cur+1, dist[i][j])
    cur = INF
    for i in range(H-1, -1, -1):
        dist[i][j] = cur = min(cur+1, dist[i][j])
ans = 0
for i in range(H):
    di = dist[i]
    for j in range(W):
        ans = max(ans, di[j])
sys.stdout.write("%d\n" % ans)