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: Wrong Answer

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))

cnt=0
while len(que)!=0:
    ln=len(que)
    for i in range(ln):
        cur=que.popleft()
        # 4方向見る
        for direction in directions:
            nxt = list(map(lambda x,y: x+y, cur, direction))
            # 壁と黒はスキップ
            if grid[nxt[0]][nxt[1]]=='*' or grid[nxt[0]][nxt[1]]=='#':
                continue
            # 白を埋める
            if grid[nxt[0]][nxt[1]]=='.':
                grid[nxt[0]][nxt[1]]='#'
                # nxtの遷移先に白があったら詰める
                if (grid[nxt[0]-1][nxt[1]]=='.'
                        or grid[nxt[0]+1][nxt[1]]=='.'
                        or grid[nxt[0]][nxt[1]-1]=='.'
                        or grid[nxt[0]][nxt[1]+1]=='.'):
                    que.append(nxt)
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
# ContestName
# URL
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def check(i, j, q, count, H, W, B, rec):
    if i < 0 or i >= H:
        return count
    if j < 0 or j >= W:
        return count
    if B[i][j] <= rec:
        return count
    B[i][j] = rec
    count += 1
    q.append((i, j))
    return count

def main():
    H, W = i2nn()
    A = ii2ss(H)
    HW = H * W
    B = [[3000] * W for _ in range(H)]
    q = []
    count = 0
    rec = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                B[i][j] = 0
                q.append((i, j))
                count += 1
    while True:
        if count >= HW:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            count = check(i-1, j, q2, count, H, W, B, rec)
            count = check(i+1, j, q2, count, H, W, B, rec)
            count = check(i, j-1, q2, count, H, W, B, rec)
            count = check(i, j+1, q2, count, H, W, B, rec)
        q = q2
        if rec >= 10:
            return

main()

Submission status: Wrong Answer

Solution code:
from queue import Queue

H, W = map(int, input().split())
A = [[-1] * W for _ in range(H)]
q = Queue()
for i in range(H):
    b = input()
    for j in range(W):
        if b[j] == '#':
            q.put((i, j, 0))
            A[i][j] = 0
ans = -1
while not q.empty():
    i, j, k = q.get()
    for x, y in [(1, 0), (0, 1), (-1, 0), (1, 0)]:
        ni = i + x
        nj = j + y
        if ni < 0 or nj < 0 or ni >= H or nj >= W:
            continue
        if A[ni][nj] >= 0:
            continue
        ans = max(ans, k + 1)
        A[ni][nj] = k + 1
        q.put((ni, nj, k + 1))
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**10
from functools import reduce

H,W = map(int,input().split())
A = []
for i in range(H):
    a = list(input())
    A.append(a)
bool = [[0 for i in range(W)] for j in range(H)]
ans =0
while True:
    flag = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" and bool[h][w]==0:
                hu = h-1
                hd = h+1
                wr = w+1
                wl = w-1
                if hu >=0:
                    A[hu][w] ="#"
                if hd <= H-1:
                    A[hd][w] ="#"
                if wr <=W-1:
                    A[h][wr] ="#"
                if wl  >= 0:
                    A[h][wl] ="#"
                bool[h][w] = 1
                flag = 1
            else:
                continue
    if flag == 0:
        break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

def copy(ll):
    nl = []
    for i in range(h):
        nl.append([])
        for j in range(w):
            nl[i].append(ll[i][j])
    return nl

nl = copy(l)
    
c = 0
while True:
    c += 1
    for i in range(h):
        p = set(l[i])
        if "." not in p:
            continue
        for j in range(w):
            if l[i][j] == "#":
                if i - 1 >= 0:
                    nl[i - 1][j] = "#"
                if i + 1 < h:
                    nl[i + 1][j] = "#"
                if j - 1 >= 0:
                    nl[i][j - 1] = "#"
                if j + 1 < w:
                    nl[i][j + 1] = "#"

    l = copy(nl)
    
    f = True
    for i in range(h):
        p = set(l[i])
        if "." in p:
            f = False
            break

    if f:
        break
        
print(c)

Submission status: Wrong Answer

Solution code:
from sys import exit
import queue
H,W = [int(n) for n in input().split()]
INF = (1 << 21)
dxy = [[1,0],[-1,0],[0,1],[0,-1]]
A = [0 for _ in range(H)]
black = []
for i in range(H):
    A[i] = list(str(input()))
    for j in range(len(A[i])):
        if(A[i][j] == "#"):
            black.append((i,j))
dis = [[H for _ in range(W)] for __ in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            for b in black:
                dis[i][j] = min(dis[i][j], abs(b[0]-i) + abs(b[1]-j))
        else:
            dis[i][j] = 0
ans = 0
for i in range(H):
    tmp = max(dis[i])
    ans = max(ans,tmp)
    # print(dis[i])
print(ans)

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
A = [0] * H
for i in range(H):
    A[i] = input()
Black = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            Black.append([i,j])
T = 0
while(1):
    New_Black = []
    for [i,j] in Black:
        if i>0 and A[i-1][j] == ".":
            A[i-1] = A[i-1][:j]+"#" + A[i-1][j+1:]
            New_Black.append([i-1,j])
        if j>0 and A[i][j-1] == ".":
            A[i] = A[i][:j-1]+"#" + A[i][j:]
            New_Black.append([i,j-1])
        if i<H-1 and A[i+1][j] == ".":
            A[i+1] = A[i+1][:j]+"#" + A[i+1][j+1:]
            New_Black.append([i+1,j])
        if j<W-1 and A[i][j+1] == ".":
            A[i] = A[i][:j+1]+"#" + A[i-1][j+2:]
            New_Black.append([i,j+1])
    Black = [a for a in New_Black]
    if len(New_Black) == 0:
        break
    T += 1
print(T)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

A = [list(map(lambda x: x == "#", input())) for i in range(H)]

arr = np.zeros((H + 2, W + 2), dtype="bool")
arr[1:-1, 1:-1] = np.array(A)

count = 0
while True:
    arr[1:-1, 1:-1] = arr[:-2, 1:-1] + arr[2:, 1:-1] + arr[1:-1, 2:] + arr[1:-1, :-2] + arr[1:-1, 1:-1]
    count += 1
    if arr[1:-1, 1:-1].all():
        break
print(count)

Submission status: Wrong Answer

Solution code:

WHITE = '.'
GRAY = '-'
BLACK = '#'

H, W = [int(i) for i in input().split()]
M = []
for i in range(H):
    M.append(list(input()))

counter = 0
while True:
    is_all_black = True
    for h in range(H):
        for w in range(W):
            if M[h][w] == BLACK:
                if h + 1 < H:
                    if M[h+1][w] == WHITE:
                        M[h+1][w] = GRAY
                if h > 0:
                    if M[h-1][w] == WHITE:
                        M[h-1][w] = GRAY
                if w + 1 < W:
                    if M[h][w+1] == WHITE:
                        M[h][w+1] = GRAY
                if w > 0:
                    if M[h][w-1] == WHITE:
                        M[h][w-1] = GRAY
    for h in range(H):
        for w in range(W):
            if M[h][w] == GRAY:
                M[h][w] = BLACK
            elif M[h][w] == WHITE:
                is_all_black = False

    counter += 1
    # print('====')
    # for m in M:
    # print(m)
    if is_all_black:
        break
print(counter)

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
A = [list(input()) for _ in range(h)]
turns = []
cnt = 0

while True:
  for i in range(h):
    for j in range(w):
      if A[i][j] == "#":
        turns.append((i+1, j))
        turns.append((i-1, j))
        turns.append((i, j+1))
        turns.append((i, j-1))
  for turn in turns:
    if 0 <= turn[0] < h and 0 <= turn[1] < w:
      A[turn[0]][turn[1]] = "#"
  turns.clear()
  flag = 0
  cnt += 1
  for i in range(h):
    for j in range(w):
      if A[i][j] == ".":
        flag = 1
  if flag == 0:
    break

print(cnt)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
l = []
count = []
for i in range(h):
  l.append(list(input()))
for i in range(h):
  count.append(l[i].count("."))
print(max(count))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
h,w=map(int,input().split())
MAP=[list(input().strip()) for _ in range(h)]
q=deque()
for i,M in enumerate(MAP):
    for j,m in enumerate(M):
        if m=='#':
            q.append((i,j,0))
delta=[(1,0),(-1,0),(0,1),(0,-1)]
ans=0
while q:
    x,y,d=q.popleft()
    ans=max(ans,d)
    for dx,dy in delta:
        if 0<=x+dx<h and 0<y+dy<w:
            if MAP[x+dx][y+dy]=='.':
                MAP[x+dx][y+dy]='#'
                q.append((x+dx,y+dy,d+1))
print(ans)

Submission status: Wrong Answer

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

A = []
P = []
for j in range(H):
    a = list(input())
    for i in range(W):
        if a[i] == '#':
            P.append([j,i])
    A.append(a)

a_t = 0
for i in range(H):
    for j in range(W):
        ans = 1000
        for p in P:
            ans = min(ans,abs(i-p[0])+abs(j-p[1]))
        a_t = max(a_t,ans)

print(a_t)

Submission status: Wrong Answer

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

print('2')

Submission status: Wrong Answer

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

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

def copy(ll):
    nl = []
    for i in range(h):
        nl.append([])
        for j in range(w):
            nl[i].append(ll[i][j])
    return nl

nl = copy(l)
    
c = 0
while True:
    c += 1
    for i in range(h):
        for j in range(w):
            if l[i][j] == "#":
                if i - 1 >= 0:
                    nl[i - 1][j] = "#"
                if i + 1 < h:
                    nl[i + 1][j] = "#"
                if j - 1 >= 0:
                    nl[i][j - 1] = "#"
                if j + 1 < w:
                    nl[i][j + 1] = "#"
                    
    l = copy(nl)
    
    f = True
    for i in range(h):
        for j in range(w):
            if l[i][j] == ".":
                f = False
                break

    if f:
        break
        
print(c)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

dh = [1, -1, 0, 0]
dw = [0, 0, 1, -1]
ans = 0

while len(q):
    ans += 1
    n = len(q)
    for i in range(n):
        h, w = q.pop()
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if nh >= H or nh < 0 or nw >= W or nw < 0:
                continue
            if A[nh][nw] == '.':
                A[nh][nw] = '#'
                q.append((nh, nw))

print(ans - 1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = list(map(int, input().split()))
f = []
q = deque()
for i in range(h):
    l = input()
    for j, c in enumerate(l):
        if c == '#':
            q.append((0, i, j))
    f.append(l)

visited = [[False] * w for _ in [0] * h]
for d, i, j in q:
    visited[i][j] = True

ans = 0
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

while q:
    d, i, j = q.popleft()
    ans = d
    for di, dj in move:
        ni, nj = i + di, j + dj
        if ni < 0 or h <= ni or nj < 0 or w <= nj:
            continue
        if visited[ni][nj]:
            continue
        visited[i][j] = True
        q.append((d + 1, ni, nj))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def is_white(h, w):
    return 0 <= h < H and 0 <= w < W and A[h][w] == '.'


stack = []
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            if is_white(h + 1, w):
                stack.append((h + 1, w))
            if is_white(h - 1, w):
                stack.append((h - 1, w))
            if is_white(h, w + 1):
                stack.append((h, w + 1))
            if is_white(h, w - 1):
                stack.append((h, w - 1))

ans = 0
while len(stack) > 0:
    ans += 1
    nexts = []
    while len(stack) > 0:
        h, w = stack.pop()
        A[h][w] = '#'
        if is_white(h + 1, w):
            nexts.append((h + 1, w))
        if is_white(h - 1, w):
            nexts.append((h - 1, w))
        if is_white(h, w + 1):
            nexts.append((h, w + 1))
        if is_white(h, w - 1):
            nexts.append((h, w - 1))
    stack = nexts
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product


def bfs():
    while q:
        i, j = q.popleft()
        for di, dj in (1, 0), (-1, 0), (0, 1), (0, -1):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0):
                continue
            dist[ni][nj] = dist[i][j] + 1
            q.append((ni, nj))


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

q = deque()
dist = [[-1] * W for _ in range(H)]
for i, j in product(range(H), range(W)):
    if A[i][j] == ".":
        continue
    q.append((i, j))
    dist[i][j] = 0
bfs()
print(max(max(row) for row in dist))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
q = deque()
A = []
for h in range(H):
    r = input()
    for w in range(W):
        if r[w] == "#":
            q.append([h, w])
    A.append([0 if s=="#" else -1 for s in r])

d = [[-1, 0], [0, -1], [0, 1], [1, 0]]
p = 0

while q:
    h, w = q.popleft()
    p = A[h][w]+1
    for dh, dw in d:
        nh = h+dh
        nw = w+dw
        if not (0 <= nh < H):
            continue
        if not (0 <= nw < W):
            continue
        if A[nh][nw] == -1:
            A[nh][nw] = p
            q.append([nh, nw])

print(p-1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000)
from collections import deque

H, W = map(int, input().split())
#配列の入力
data = [list(input()) for _ in range(H)]

memo = [[-1 for _ in range(W)]for _ in range(H)]
que = deque()

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

offset = ((-1, 0), (1, 0), (0, -1), (0, 1))
ans = 0
while que:
    now_h, now_w = que.popleft()
    for nh, nw in offset:
        if now_h+nh < 0 or H-1 < now_h+nh or now_w+nw < 0 or W-1 < now_w+nw:
            continue

        if memo[now_h+nh][now_w+nw] >= 0:
            continue

        memo[now_h+nh][now_w+nw] = memo[now_h][now_w]+1
        ans = max(ans, memo[now_h+nh][now_w+nw])
        que.append((now_h+nh,now_w+nw))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000)
from collections import deque

H, W = map(int, input().split())
#配列の入力
data = [list(input()) for _ in range(H)]

memo = [[-1 for _ in range(W)]for _ in range(H)]
que = deque()

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

offset = ((-1, 0), (1, 0), (0, -1), (0, 1))
while que:
    now_h, now_w = que.popleft()
    for nh, nw in offset:
        if now_h+nh < 0 or H-1 < now_h+nh or now_w+nw < 0 or W-1 < now_w+nw:
            continue

        if memo[now_h+nh][now_w+nw] >= 0:
            continue

        memo[now_h+nh][now_w+nw] = memo[now_h][now_w]+1
        que.append((now_h+nh,now_w+nw))


ans = -1
for h in range(H):
    ans = max(ans, max(memo[h]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


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


def main():
    from collections import deque

    h, w = input_int_list()
    grid = []
    grid.append(["@"] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
    grid.append(["@"] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    dq = deque()
    visited = set()
    # すべての"#"をdequeに入れる
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == "#":
                dq.append((i, j, 0))
                visited.add((i, j))
    ans = 0
    # 幅優先探索
    while dq:
        i, j, d = dq.popleft()
        for di, dj in direction:
            if grid[i + di][j + dj] == "." and (i + di, j + dj) not in visited:
                dq.append((i + di, j + dj, d + 1))
                visited.add((i + di, j + dj))
                ans = max(ans, d + 1)

    print(ans)
    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


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


def main():
    h, w = input_int_list()
    grid = []
    grid.append(["@"] * (w + 2))
    for _ in range(h):
        grid.append(["@"] + list(input()) + ["@"])
    grid.append(["@"] * (w + 2))

    # 幅優先探索で すべてを"#"に変える。
    # かかった手数分が答え
    cnt = 1
    direction = ((0, 1), (1, 0), (-1, 0), (0, -1))
    while True:
        do_swap = False
        for i in range(1, h + 1):
            for j in range(1, w + 1):
                if grid[i][j] == "#" or grid[i][j] == cnt - 1:
                    for di, dj in direction:
                        if grid[i + di][j + dj] == ".":
                            do_swap = True
                            grid[i + di][j + dj] = cnt
                    grid[i][j] = "@"
        if do_swap:
            cnt += 1
        else:
            break

    print(cnt - 1)

    return


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
readline = stdin.readline
H,W = map(int,input().split())
A = ['' for i in range(H)]
colors = [[-2 for j in range(W)] for i in range(H)]
q = []
for i in range(H):
    A[i] = readline()[:-1]
    # print(A[i])
    for j,color in enumerate(A[i]):
        # print(j,color)
        colors[i][j] = 0 if color == '#' else -1
        if '#' == color:
            q.append([i,j,0])
            colors[i][j] = 0
# for i in colors:
#     print(i)
mx = 0
direction = [[1,0],[0,1],[-1,0],[0,-1]]

while len(q) > 0:
    # print(q)
    tmp = [y,x,op] = q.pop(0)
    mx = max(mx,op)
    if colors[y][x] >= 0 and mx > 0: continue
    for [dx,dy] in direction:
        ny,nx = y + dy , x + dx
        if  0 <= ny and ny < H and 0 <= nx and nx < W:
            if A[ny][nx] == '#' or colors[ny][nx] >= 0:
                continue
            q.append([ny,nx,op+1])
            colors[y][x] = op+1
print(mx)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = ['' for i in range(H)]
colors = [[-2 for j in range(W)] for i in range(H)]
q = []
for i in range(H):
    A[i] = list(input())
    for j,color in enumerate(A[i]):
        colors[i][j] = 0 if color == '#' else -1
        if '#' == color:
            q.append([i,j,0])
            colors[i][j] = 0
# for i in colors:
#     print(i)
mx = 0
direction = [[1,0],[0,1],[-1,0],[0,-1]]

while len(q) > 0:
    # print(q)
    tmp = [y,x,op] = q.pop(0)
    mx = max(mx,op)
    if colors[y][x] >= 0 and mx > 0: continue
    for [dx,dy] in direction:
        ny,nx = y + dy , x + dx
        if  0 <= ny and ny < H and 0 <= nx and nx < W:
            if A[ny][nx] == '#' or colors[ny][nx] >= 0:
                continue
            q.append([ny,nx,op+1])
            colors[y][x] = op+1
print(mx)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = ['' for i in range(H)]
colors = [[-2 for j in range(W)] for i in range(H)]
q = []
for i in range(H):
    A[i] = list(input())
    for j,color in enumerate(A[i]):
        colors[i][j] = 0 if color == '#' else -1
        if '#' == color:
            q.append([i,j,0])
# for i in colors:
#     print(i)
mx = 0
direction = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    # print(q)
    tmp = [y,x,op] = q.pop(0)
    mx = max(mx,op)
    if colors[y][x] >= 0 and mx > 0: continue
    colors[y][x] = op
    for [dx,dy] in direction:
        ny,nx = y + dy , x + dx
        if  0 <= ny and ny < H and 0 <= nx and nx < W:
            if A[ny][nx] == '#' or colors[ny][nx] >= 0:
                continue
            q.append([ny,nx,op+1])
print(mx)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = ['' for i in range(H)]
colors = [[-2 for j in range(W)] for i in range(H)]
q = []
for i in range(H):
    A[i] = list(input())
    for j,color in enumerate(A[i]):
        colors[i][j] = 0 if color == '#' else -1
        if '#' == color:
            q.append([i,j,0])
# for i in colors:
#     print(i)
mx = 0
direction = [[1,0],[0,1],[-1,0],[0,-1]]
while len(q) > 0:
    # print(q)
    tmp = [y,x,op] = q.pop(0)
    mx = max(mx,op)
    if colors[y][x] > 0: continue
    colors[y][x] = op
    for [dx,dy] in direction:
        ny,nx = y + dy , x + dx
        if  0 <= ny and ny < H and 0 <= nx and nx < W:
            if A[ny][nx] == '#' or colors[ny][nx] >= 0:
                continue
            q.append([ny,nx,op+1])
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part
from collections import deque
H,W=MI()
route=[list(I()) for _ in range(H)]
d=deque()
for h in range(H):
    for w in range(W):
        if route[h][w]=='#':
            d.append([h,w])
cnt=0
while d:
    l=list(d)
    d.clear()
    for Y,X in l:
        for y,x in [[Y-1,X],[Y+1,X],[Y,X-1],[Y,X+1]]:
            if 0<=y<H and 0<=x<W:
                if route[y][x]=='.':
                    route[y][x]='#'
                    d.append([y,x])
    cnt+=1
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
L = ["*" + input() + "*" for i in range(H)]
L = ["*" * (W + 2)] + L + ["*" * (W + 2)]
Q = [(i,j,0) for i in range(1, H + 1) for j in range(1, W + 1) if L[i][j] == "#"]
A = [[-2] + [-1] * W + [-2] for i in range(H)]
A = [[-2] * (W + 2)] + A + [[-2] * (W + 2)]
ans = 0
while len(Q) > 0:
  i, j, n = Q.pop(0)
  A[i][j] = n
  ans = max(ans, n)
  if A[i-1][j] == -1:
    Q.append([i-1, j, n + 1])
  if A[i+1][j] == -1:
    Q.append([i+1, j, n + 1])
  if A[i][j-1] == -1:
    Q.append([i, j-1, n + 1])
  if A[i][j+1] == -1:
    Q.append([i, j+1, n + 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
B = {(i, j) for i in range(H) for j in range(W) if A[i][j] == "#"}
ans = 0
for i in range(H):
  for j in range(W):
    if A[i][j] != "#":
      C = 5000
      for k in B:
        a,b = k
        C = min(C, (abs(a - i) + abs(b - j)))
      ans = max(ans, C)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [input() for _ in range(H)]
B = {(i, j) for i in range(H) for j in range(W) if A[i][j] == "#"}
ans = 0
for i in range(H):
  for j in range(W):
    C = []
    for k in B:
      a,b = k
      C.append(abs(a - i) + abs(b - j))
    ans = max(ans, min(C))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = ["*" + input() + "*" for _ in range(H)]
A = ["*" * (W + 2)] + A + ["*" * (W + 2)]
ans = 0
for i in range(1, H + 1):
  for j in range(1, W + 1):
    log = set()
    task = [[i, j, 0]]
    while len(task) > 0:
      a,b,n = task.pop(0)
      #print(a,b,A[a][b])
      log.add((a, b))
      if A[a][b] == "#": 
        #print(n)
        ans = max(ans, n)
        break
      if A[a-1][b] != "*" and (a-1, b) not in log:
        task.append([a-1, b, n + 1])
      if A[a+1][b] != "*" and (a+1, b) not in log:
        task.append([a+1, b, n + 1])
      if A[a][b-1] != "*" and (a, b-1) not in log:
        task.append([a, b-1, n + 1])
      if A[a][b+1] != "*" and (a, b+1) not in log:
        task.append([a, b+1, n + 1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import Queue

input = sys.stdin.readline
h, w = map(int, input().split())
matrix = dict()
queue = Queue()
for i in range(h):
    cells = list(input().rstrip("\n"))
    for j, cell in enumerate(cells):
        if cell == "#":
            matrix[str(i) + "_" + str(j)] = 0
            queue.put((i, j))
        else:
            matrix[str(i) + "_" + str(j)] = -1
while not queue.empty():
    i, j = queue.get(block=False)
    for i_diff, j_diff in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        i_current = i + i_diff
        j_current = j + j_diff
        if (
            0 <= i_current < h
            and 0 <= j_current < w
            and matrix[str(i_current) + "_" + str(j_current)] == -1
        ):
            matrix[str(i_current) + "_" + str(j_current)] = (
                matrix[str(i) + "_" + str(j)] + 1
            )
            queue.put((i_current, j_current))

max_step = max(matrix.values())
print(max_step)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from queue import Queue

input = sys.stdin.readline
h, w = map(int, input().split())
matrix = defaultdict(lambda: -1)
queue = Queue()
for i in range(h):
    cells = list(input().rstrip("\n"))
    for j, cell in enumerate(cells):
        if cell == "#":
            matrix[str(i) + "_" + str(j)] = 0
            queue.put((i, j))
while not queue.empty():
    i, j = queue.get(block=False)
    for i_diff, j_diff in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        i_current = i + i_diff
        j_current = j + j_diff
        if (
            0 <= i_current < h
            and 0 <= j_current < w
            and matrix[str(i_current) + "_" + str(j_current)] == -1
        ):
            matrix[str(i_current) + "_" + str(j_current)] = (
                matrix[str(i) + "_" + str(j)] + 1
            )
            queue.put((i_current, j_current))

max_step = max(matrix.values())
print(max_step)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+i
            y0 = y+j
            if not counts[x0][y0]:
                counts[x0][y0] = True
                q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+i
            y0 = y+j
            if not counts[x0][y0]:
                counts[x0][y0] = True
                q.append([x0, y0, z+1])
    print(z)

cal()

Submission status: Time Limit Exceeded

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

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while len(q) > 0:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+i
            y0 = y+j
            if not counts[x0][y0]:
                counts[x0][y0] = True
                q.append([x0, y0, z+1])
    print(z)

cal()