Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import queue

h,w = map(int,input().split())
city = [list(input()) for i in range(h)]
count = [[-1]*w for i in range(h)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
q = queue.Queue()
for i in range(h):
    for j in range(w):
      if city[i][j] == "#":
        q.put([i,j])
        count[i][j] = 0

def black(): 
  while not q.empty():
    p = q.get()
    for i in range(4):
      for j in range(4):
        ny = p[0] + dy[i]
        nx = p[1] + dx[i]
        if 0 <= ny < h and 0 <= nx < w and city[ny][nx] == "." and count[ny][nx] == -1:
          q.put([ny,nx])
          count[ny][nx] = count[p[0]][p[1]] + 1
black()
nums = []
for i in range(h):
  for j in range(w):
    nums.append(count[i][j])
    
print(max(nums))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
graph = [[2000 for i in range(w)] for j in range(h)]
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

#graph => そこまでの距離を保存した二次元配列　grid=>与えられた迷路
def bfs(que):
    finished = set()
    while que:
        x , y, cost = que.popleft()
        if y*w+x not in finished and graph[y][x] > cost:
            finished.add(y*w+x)
            graph[y][x] = cost
            if check(y,x+1):
                que.append([x+1,y,cost+1])
            if check(y+1,x):
                que.append([x, y+1, cost+1])
            if check(y,x-1):
                que.append([x-1,y,cost+1])
            if check(y-1,x):
                que.append([x,y-1,cost+1])
for i in range(h):
    grid.append(list(input()))
que = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            que.append((j,i,0))
bfs(que)
ans = 0
for i in range(h):
    ans = max(ans, max(graph[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
mapl = [list(input()) for i in range(h)]
searched = [[False for i in range(w)] for j in range(h)]
move = ((0,1),(1,0),(-1,0),(0,-1))

import queue
s_queue = queue.Queue()

for y in range(h):
    for x in range(w):
        if(mapl[y][x]=='#'):
            s_queue.put([x,y,0])
            searched[y][x] = True



def bfs():
    last=0
    
    while(not s_queue.empty()):
        y,x,cnt = s_queue.get()
        for a,b in move:
            ny,nx=y+a,x+b
            
            if(ny<0 or ny>=h or nx<0 or nx>=w):
                continue
            if(searched[ny][nx]):
                continue
            searched[ny][nx]=True
            last = cnt + 1
            s_queue.put([ny,nx,last])
    return last

cnt = bfs()
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
mapl = [list(input()) for i in range(h)]
searched = [[False for i in range(w)] for j in range(h)]
move = ((0,1),(1,0),(-1,0),(0,-1))
s_queue = []
for y in range(h):
    for x in range(w):
        if(mapl[y][x]=='#'):
            s_queue.append([y,x,0])
            searched[y][x] = True


def bfs():
    last=0
    
    while(len(s_queue)>0):
        y,x,cnt = s_queue.pop(0)
        for a,b in move:
            ny,nx=y+a,x+b
            
            if(ny<0 or ny>=h or nx<0 or nx>=w):
                continue
            if(searched[ny][nx]):
                continue
            searched[ny][nx]=True
            last = cnt + 1
            s_queue.append([ny,nx,last])
    return last

cnt = bfs()
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
chk=[]
v=[[False]*w for _ in range(h)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
cnt=0
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            v[i][j]=True
            chk.append((i,j))
while chk:
    achk=[]
    cnt+=1
    for nx,ny in chk:
        for dx,dy in d:
            x=nx+dx
            y=ny+dy
            if x>=0 and x<=h-1 and y>=0 and y<=w-1:
                if v[x][y]==False:
                    v[x][y]=True
                    achk.append((x,y))
    chk=achk
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
chk=[]
d=[[1,0],[-1,0],[0,1],[0,-1]]
cnt=0
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            chk.append((i,j))
while chk:
    achk=[]
    cnt+=1
    for nx,ny in chk:
        for dx,dy in d:
            x=nx+dx
            y=ny+dy
            if x>=0 and x<=h-1 and y>=0 and y<=w-1:
                if a[x][y]=='.':
                    a[x][y]='#'
                    achk.append((x,y))
    chk=achk
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
chk=[[] for _ in range(10**6)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
cnt=0
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            chk[0].append([i,j])
while chk[cnt]:
    for nx,ny in chk[cnt]:
        for dx,dy in d:
            x=nx+dx
            y=ny+dy
            if x>=0 and x<=h-1 and y>=0 and y<=w-1:
                if a[x][y]=='.':
                    a[x][y]='#'
                    chk[cnt+1].append([x,y])
    if chk[cnt+1]:
        cnt+=1
    else:
        break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(input()) for _ in range(h)]
chk=[[] for _ in range(10**6)]
d=[[1,0],[-1,0],[0,1],[0,-1]]
cnt=0
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            chk[0].append([i,j])
while chk[cnt]:
    nx,ny=chk[cnt].pop()
    for dx,dy in d:
        x=nx+dx
        y=ny+dy
        if x>=0 and x<=h-1 and y>=0 and y<=w-1:
            if a[x][y]=='.':
                a[x][y]='#'
                chk[cnt+1].append([x,y])
    if chk[cnt]:
        continue
    elif chk[cnt+1]:
        cnt+=1
    else:
        break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    S=[]
    
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S.append(list(input()))
    
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                q.put((i,j))
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    dis=[[0]*W for _ in range(H)]
    
    while not q.empty():
        ii,jj=q.get()
        d=dis[ii][jj]
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            
            if 0<=nxt_i<=H-1:
                if 0<=nxt_j<=W-1:
                    if S[nxt_i][nxt_j]==".":
                        q.put((nxt_i,nxt_j))
                        S[nxt_i][nxt_j]="#"
                        dis[nxt_i][nxt_j]=d+1
    print(d)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    S=[]
    
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S.append(list(input()))
    
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                q.put((i,j,0))
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            
            if 0<=nxt_i<=H-1:
                if 0<=nxt_j<=W-1:
                    if S[nxt_i][nxt_j]==".":
                        q.put((nxt_i,nxt_j,d+1))
                        S[nxt_i][nxt_j]="#"
    print(d)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    S=[]
    
    A=[[1]*(W)for _ in range(H)]
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S.append(list(input()))
    
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                q.put((i,j,0))
            else:
                A[i][j]=0  
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            
            if 0<=nxt_i<=H-1:
                if 0<=nxt_j<=W-1:
                    if A[nxt_i][nxt_j]==0:
                        q.put((nxt_i,nxt_j,d+1))
                        A[nxt_i][nxt_j]=1
    print(d)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    S=[]
    
    A=[[1]*(W+2)for _ in range(H+2)]
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S.append(list(input()))
    
    for i in range(H):
        for j in range(W):
            if S[i][j]=="#":
                q.put((i+1,j+1,0))
            else:
                A[i+1][j+1]=0  
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if A[nxt_i][nxt_j]==0:
                q.put((nxt_i,nxt_j,d+1))
                A[nxt_i][nxt_j]=1
    print(d)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    A=[[1]*(W+2)for _ in range(H+2)]
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S=input()
        for j in range(W):
            if S[j]=="#":
                q.put((i+1,j+1,0))
            else:
                A[i+1][j+1]=0  
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if A[nxt_i][nxt_j]==0:
                q.put((nxt_i,nxt_j,d+1))
                A[nxt_i][nxt_j]=1
    print(d)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    input = sys.stdin.readline
    
    H,W=map(int, input().split())
    A=[["#"]*(W+2)for _ in range(H+2)]
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S=input()
        for j in range(W):
            A[i+1][j+1]=S[j]
            if S[j]=="#":
                q.put((i+1,j+1,0))
                
    
    

    
    inf=-1

                
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    ans=0
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if A[nxt_i][nxt_j]==".":
                q.put((nxt_i,nxt_j,d+1))
                A[nxt_i][nxt_j]="#"
    print(d)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def main():
    H,W=map(int, input().split())
    A=[["#"]*(W+2)for _ in range(H+2)]
    import queue
    q=queue.Queue()
    
    for i in range(H):
        S=input()
        for j in range(W):
            A[i+1][j+1]=S[j]
            if S[j]=="#":
                q.put((i+1,j+1,0))
                
    
    

    
    inf=-1

                
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    ans=0
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if A[nxt_i][nxt_j]==".":
                q.put((nxt_i,nxt_j,d+1))
                A[nxt_i][nxt_j]="#"
    print(d)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:
def f(q, t, count, i, j):
    if t[i][j] == '.':
        t[i][j] = '#'
        q.append((i, j))
        used[(i, j)] = count

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

t = [['-'] * (w+2)]
for _ in range(h):
    t.append([ '-'] + list(input()) + ['-'])
t.append(['-'] * (w+2))

q = []
used = {}
for i, row in enumerate(t):
    for j, col in enumerate(row):
        if t[i][j] == '#':
            q.append((i, j))
            used[(i, j)] = 0

while len(q) != 0:
    i, j = q.pop(0)
    count = used[(i, j)]
    f(q, t, count+1, i-1, j)
    f(q, t, count+1, i+1, j)
    f(q, t, count+1, i, j-1)
    f(q, t, count+1, i, j+1)

print(max(used.values()))

Submission status: Time Limit Exceeded

Solution code:

def f(q, t, count, i, j):
    if t[i][j] == '.':
        t[i][j] = '#'
        q.append((i, j))
        used[(i, j)] = count

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

t = [['-'] * (w+2)]
for _ in range(h):
    t.append([ '-'] + list(input()) + ['-'])
t.append(['-'] * (w+2))

q = []
used = {}
for i, row in enumerate(t):
    for j, col in enumerate(row):
        if t[i][j] == '#':
            q.append((i, j))
            used[(i, j)] = 0

while len(q) != 0:
    i, j = q.pop(0)
    count = used[(i, j)]
    f(q, t, count+1, i-1, j)
    f(q, t, count+1, i+1, j)
    f(q, t, count+1, i, j-1)
    f(q, t, count+1, i, j+1)

print(max(used.values()))

Submission status: Time Limit Exceeded

Solution code:
#AGC033-A Darker and Darker
"""
マンハッタン距離で最も白マスと黒マスの遠いところが答え
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#迷路plane
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

def dfs(i,j):
    deq = deque([[i,j,1]])
    visited = [[False]*W for _ in range(H)]
    while deq:
        h,w,now = deq.popleft()
        visited[h][w] = True
        for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not (0 <= h+a < H and 0 <= w+b < W):continue
            if visited[h+a][w+b]:continue
            if maze[h+a][w+b] == "#":return now
            else:deq.append([h+a,w+b,now+1])

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            ans = max(ans,dfs(i,j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#AGC033-A Darker and Darker
"""
マンハッタン距離で最も白マスと黒マスの遠いところが答え
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#迷路plane
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

def dfs(i,j):
    deq = deque([[i,j,1]])
    while deq:
        h,w,now = deq.popleft()
        for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not (0 <= h+a < H and 0 <= w+b < W):continue
            if maze[h+a][w+b] == "#":return now
            else:deq.append([h+a,w+b,now+1])

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            ans = max(ans,dfs(i,j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make(i, j):
    if a[i][j] == ".":
        next_queue.put([i, j])
        a[i][j] = "#"
        return 0
    return 0

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
# print(a)
import queue
next_visit = queue.Queue()

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            next_visit.put([i, j])
cnt = 0
while True:
    next_queue = queue.Queue()
    while not next_visit.empty():
        [i, j] = next_visit.get()
        if 0 < i:
            cnt += make(i-1, j)
        if 0 < j:
            cnt += make(i, j-1)
        if i < h-1:
            cnt += make(i+1, j)
        if j < w-1:
            cnt += make(i, j+1)
    next_visit = next_queue
    cnt += 1
    if next_queue.empty():
        break
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

black_idx = []
white_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == ".":
            white_idx.append([h,w])
        else:
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

d = deque(black_idx)
while d:
    y, x = d.popleft()
    for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1], [int(y)-1, int(x)], [int(y), int(x)-1]):
        if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
            new_cost = distance[y][x] + 1
            if new_cost < distance[new_y][new_x]: # 距離更新が発生した点だけdequeにappend
                distance[new_y][new_x] = new_cost
                d.append([new_y, new_x])

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, distance[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

black_idx = set()
white_idx = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == ".":
            white_idx.add((h,w))
        else:
            black_idx.add((h,w))

ans = 0
for white in white_idx:
    tmp = float("inf")
    for black in black_idx:
        tmp = min(tmp, abs(white[0] - black[0]) + abs(white[1] - black[1]))
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

black_idx = []
white_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == ".":
            white_idx.append([h,w])
        else:
            black_idx.append([h,w])

ans = 0
for white in white_idx:
    tmp = float("inf")
    for black in black_idx:
        tmp = min(tmp, abs(white[0] - black[0]) + abs(white[1] - black[1]))
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

black_idx = []
white_idx = []
for h in range(H):
    for w in range(W):
        if A[h][w] == ".":
            white_idx.append([h,w])
        else:
            black_idx.append([h,w])

distance = [[float("inf")]*W for _ in range(H)]
for b in black_idx:
    distance[b[0]][b[1]] = 0

for b in black_idx:
    d = deque([[b[0], b[1]]])
    while d:
        y, x = d.popleft()
        for new_y, new_x in ([int(y)+1, int(x)], [int(y), int(x)+1], [int(y)-1, int(x)], [int(y), int(x)-1]):
            if 0 <= new_y <= H-1 and 0 <= new_x <= W-1:
                new_cost = distance[y][x] + 1
                if new_cost < distance[new_y][new_x]: # 距離更新が発生した点だけdequeにappend
                    distance[new_y][new_x] = new_cost
                    d.append([new_y, new_x])

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, distance[h][w])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque


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


def bfs(starts):
    moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
    dists = [[-1] * W for _ in range(H)]
    max_dist = 0
    que = deque()
    for start in starts:
        dists[start[0]][start[1]] = 0
        que.append(start)
    while len(que):
        ch, cw = que.popleft()
        for dh, dw in moves:
            nh, nw = ch + dh, cw + dw
            if (    0 <= nh < H 
                and 0 <= nw < W 
                and dists[nh][nw] == -1):
                dists[nh][nw] = dists[ch][cw] + 1
                que.append((nh, nw))
                max_dist = max(max_dist, dists[nh][nw])
    return max_dist


def solve():
    starts = ((i, j) for i in range(H) for j in range(W) if A[i][j] == '#')
    print(bfs(starts))


solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque


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


def bfs(starts):
    moves = ((1, 0), (0, 1), (-1, 0), (0, -1))
    dists = [[-1] * W for _ in range(H)]
    que = deque()
    for start in starts:
        dists[start[0]][start[1]] = 0
        que.append(start)
    while len(que):
        ch, cw = que.popleft()
        for dh, dw in moves:
            nh, nw = ch + dh, cw + dw
            if (    0 <= nh < H 
                and 0 <= nw < W 
                and dists[nh][nw] == -1):
                dists[nh][nw] = dists[ch][cw] + 1
                que.append((nh, nw))
    return max([max(i) for i in dists])


def solve():
    starts = ((i, j) for i in range(H) for j in range(W) if A[i][j] == '#')
    print(bfs(starts))


solve()

Submission status: Time Limit Exceeded

Solution code:


def main():
    H,W=map(int, input().split())
    A=[["#"]*(W+2)for _ in range(H+2)]
    
    for i in range(H):
        S=input()
        for j in range(W):
            A[i+1][j+1]=S[j]
    
    
    
    import queue
    q=queue.Queue()
    
    inf=-1
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j]=="#":
                q.put((i,j,0))
                
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    ans=0
    
    while not q.empty():
        ii,jj,d=q.get()
        ans=max(ans,d)
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if A[nxt_i][nxt_j]==".":
                q.put((nxt_i,nxt_j,d+1))
                A[nxt_i][nxt_j]="#"
    print(ans)

                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    H,W=MI()
    A=[["#"]*(W+2)for _ in range(H+2)]
    
    for i in range(H):
        S=input()
        for j in range(W):
            A[i+1][j+1]=S[j]
    
    
    
    import queue
    q=queue.Queue()
    
    inf=-1
    dMap=[[inf]*(W+2)for _ in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j]=="#":
                q.put((i,j,0))
                dMap[i][j]=0
                
    for i in range(H+2):
        dMap[i][0]=0
        dMap[i][-1]=0
        
    for j in range(W+2):
        dMap[0][j]=0
        dMap[-1][j]=0
        
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if dMap[nxt_i][nxt_j]==inf:
                q.put((nxt_i,nxt_j,d+1))
                dMap[nxt_i][nxt_j]=d+1
         
                
    ans=0
    for i in range(H+2):
        temp=max(dMap[i])
        ans=max(temp,ans)
    print(ans)
                
                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    H,W=MI()
    A=[]
    A.append(list("#"*(W+2)))
    for i in range(H):
        A.append(list("#"+input()+"#"))
    A.append(list("#"*(W+2)))
    
    
    import queue
    q=queue.Queue()
    
    inf=-1
    dMap=[[inf]*(W+2)for _ in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j]=="#":
                q.put((i,j,0))
                dMap[i][j]=0
                
    for i in range(H+2):
        dMap[i][0]=0
        dMap[i][-1]=0
        
    for j in range(W+2):
        dMap[0][j]=0
        dMap[-1][j]=0
        
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    

    while not q.empty():
        ii,jj,d=q.get()
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if dMap[nxt_i][nxt_j]==inf:
                q.put((nxt_i,nxt_j,d+1))
                dMap[nxt_i][nxt_j]=d+1
                
    ans=0
    for i in range(H+2):
        temp=max(dMap[i])
        ans=max(temp,ans)
    print(ans)
                
                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    H,W=MI()
    A=[]
    A.append(list("#"*(W+2)))
    for i in range(H):
        A.append(list("#"+input()+"#"))
    A.append(list("#"*(W+2)))
    
    
    import queue
    q=queue.Queue()
    
    inf=-1
    dMap=[[inf]*(W+2)for _ in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j]=="#":
                q.put((i,j,0))
                dMap[i][j]=0
                
    for i in range(H+2):
        dMap[i][0]=0
        dMap[i][-1]=0
        
    for j in range(W+2):
        dMap[0][j]=0
        dMap[-1][j]=0
        
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    ans=0
    while not q.empty():
        ii,jj,d=q.get()
        dMap[ii][jj]=d
        ans=max(ans,dMap[ii][jj])
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if dMap[nxt_i][nxt_j]==inf:
                q.put((nxt_i,nxt_j,d+1))
                
    print(ans)
                
                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W=MI()
    A=[]
    A.append(list("#"*(W+2)))
    for i in range(H):
        A.append(list("#"+input()+"#"))
    A.append(list("#"*(W+2)))
    
    
    import queue
    q=queue.Queue()
    
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j]=="#":
                q.put((i,j,0))
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    inf=10**10
    dMap=[[inf]*(W+2)for _ in range(H+2)]
    
    ans=0
    while not q.empty():
        ii,jj,d=q.get()
        dMap[ii][jj]=min(dMap[ii][jj],d)
        ans=max(ans,dMap[ii][jj])
        for k in range(4):
            nxt_i=ii+dx[k]
            nxt_j=jj+dy[k]
            if dMap[nxt_i][nxt_j]==inf:
                if A[nxt_i][nxt_j]==".":
                    q.put((nxt_i,nxt_j,d+1))
                
    print(ans)
                
                
    
            

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

d = deque()
op = [[-1] * w for i in range(h)]

for i in range(h):
    s = input().rstrip()
    for j in range(len(s)):
        if s[j] == '#':
            d.append((i, j, 0))

while d:
    i, j, step = d.popleft()

    if op[i][j] != -1:
        continue
    else:
        op[i][j] = step

    if i > 0:
        d.append((i-1, j, step+1))
    if i < h-1:
        d.append((i+1, j, step+1))
    if j > 0:
        d.append((i, j-1, step+1))
    if j < w-1:
        d.append((i, j+1, step+1))

print(max([max(op[i]) for i in range(h)]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
G=[["#"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["#"]+list(input())+["#"]
X=deque()
Y=deque()
V=[[0]*(w+2) for i in range(h+2)]
V[0]=[0]*(w+2)
for i in range(1,h+1):
  V[i]=[0]+[10**7]*w+[0]
V[h+1]=[0]*(w+2)
for i in range(1,h+1):
  for j in range(1,w+1):
    if G[i][j]=="#":
      X.append(i)
      Y.append(j)
      V[i][j]=0
XX=[-1,0,0,1]
YY=[0,-1,1,0]
while len(X)!=0:
  x=X[0]
  y=Y[0]
  X.popleft()
  Y.popleft()
  for i in range(4):
    if V[x+XX[i]][y+YY[i]]==10**7:
      V[x+XX[i]][y+YY[i]]=V[x][y]+1
      X.append(x+XX[i])
      Y.append(y+YY[i])
ans=0
for i in range(h+2):
  for j in range(w+2):
    if V[i][j]>ans:
      ans=V[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
l = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            l.append([i,j,0])
que = deque(l)    
while que:
    s, t, cost = que.popleft()
    for di, dj in dd:
        xi = s + di
        yj = t + dj
        if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == "#":
            continue
        S[xi][yj] = "#"
        que.append([xi, yj, cost + 1])
print(cost)

Submission status: Time Limit Exceeded

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

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

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
l = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            l.append([i,j,0])
que = deque(l)    
ans = 0
while que:
    s, t, cost = que.popleft()
    for di, dj in dd:
        xi = s + di
        yj = t + dj
        if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == "#":
            continue
        S[xi][yj] = "#"
        que.append([xi, yj, cost + 1])
print(cost)

Submission status: Time Limit Exceeded

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

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

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
l = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            l.append((i,j,0))
que = deque(l)    
ans = 0
while que:
    s, t, cost = que.popleft()
    for di, dj in dd:
        xi = s + di
        yj = t + dj
        if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == "#":
            continue
        S[xi][yj] = "#"
        que.append((xi, yj, cost + 1))
print(cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dd = ((-1, 0), (0, -1), (1, 0), (0, 1))
l = []
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            l.append([i,j,0])
que = deque(l)    
ans = 0
while que:
    s, t, cost = que.popleft()
    for di, dj in dd:
        xi = s + di
        yj = t + dj
        if (not 0 <= xi < H) or (not 0 <= yj < W) or S[xi][yj] == "#":
            continue
        S[xi][yj] = "#"
        que.append((xi, yj, cost + 1))
print(cost)