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:
# -*- coding: utf-8 -*-
# 18:01 -> 18:36 (give up. TLE)
from collections import deque

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

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

A = []
first_black = []

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

for x,y in first_black:
    A[x][y] = 0

black_deque = deque()
black_deque.extend(first_black)

while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and \
           0 <= new_y < W and \
           A[new_x][new_y] == '.':
            black_deque.append((new_x, new_y))
            A[new_x][new_y] = depth+1

print(depth)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 
from collections import deque

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

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

A = []
first_black = []

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

for x,y in first_black:
    A[x][y] = 0

black_deque = deque()
black_deque.extend(first_black)

max_depth = 0
while len(black_deque) != 0:
    x,y = black_deque.popleft()
    depth = A[x][y]
    max_depth = max(max_depth, depth)
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and \
           0 <= new_y < W and \
           A[new_x][new_y] == '.':
            black_deque.append((new_x, new_y))
            A[new_x][new_y] = depth+1

print(depth)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 18:01 -> 
from collections import deque

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

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

A = []
first_black = []

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

black_deque = deque()
black_deque.extend(first_black)

max_depth = 0
while len(black_deque) != 0:
    x,y = black_deque.popleft()
    if A[x][y] == '#':
        depth = 0
    else:
        depth = A[x][y]
    max_depth = max(max_depth, depth)
    for k in range(4):
        new_x = x+dx[k]
        new_y = y+dy[k]
        if 0 <= new_x < H and \
           0 <= new_y < W and \
           A[new_x][new_y] == '.':
            black_deque.append((new_x, new_y))
            A[new_x][new_y] = depth+1
            
print(depth)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(q):
    ans = 0
    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 0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0:
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1
                ans = max(ans, dist[ni][nj])
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(q):
    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 0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0:
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1


H, W = map(int, input().split())
field = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            dist[i][j] = 0
            q.append((i, j))
bfs(q)
print(max(v for row in dist for v in row))

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
imput = sys.stdin.readline
h,w = map(int,input().split())
visited=[[False]*(w+2)] + [[False]+[True]*w+[False] for _ in range(h)] +[[False]*(w+2)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i+1][j+1] = False
            q.put([i+1,j+1,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        x,y = i+di,j+dj
        if visited[x][y]:
            visited[x][y] = False
            q.put([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
# AGC033 A-Darker and Darker
from collections import deque
h,w = map(int,input().split())
visited=[[False]*(w+2)] + [[False]+[True]*w+[False] for _ in range(h)] +[[False]*(w+2)]
q = deque()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i+1][j+1] = False
            q.append([i+1,j+1,0])
            
while q!=deque():
    i,j,cost = q.popleft()
    for di,dj in t:
        x,y = i+di,j+dj
        if visited[x][y]:
            visited[x][y] = False
            q.append([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
visited=[[False]*(w+2)] + [[False]+[True]*w+[False] for _ in range(h)] +[[False]*(w+2)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i+1][j+1] = False
            q.put([i+1,j+1,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        x,y = i+di,j+dj
        if visited[x][y]:
            visited[x][y] = False
            q.put([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
visited=[[1]*(w+2)] + [[1]+[0]*w+[1] for _ in range(h)] +[[1]*(w+2)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i+1][j+1] = 1
            q.put([i+1,j+1,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        x,y = i+di,j+dj
        if visited[x][y] == 0:
            visited[x][y] = 1
            q.put([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
# AGC033 A-Darker and Darker
import queue
h,w = map(int,input().split())
visited=[[0]*w for _ in range(h)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i][j] = 1
            q.put([i,j,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        x,y = i+di,j+dj
        if (0<=x<h) and (0<=y<w):
            if visited[x][y] == 0:
                visited[x][y] = 1
                q.put([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
visited=[[0]*w for _ in range(h)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i][j] = 1
            q.put([i,j,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        x,y = i+di,j+dj
        if (0<=x<h) and (0<=y<w):
            if visited[x][y] == 0:
                visited[x][y] = 1
                q.put([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
# AGC033 A-Darker and Darker
import queue
h,w = map(int,input().split())
visited=[[0]*w for _ in range(h)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i][j] = 1
            q.put([i,j,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        x,y = i+di,j+dj
        if (0<=x<h) and (0<=y<w):
            if visited[x][y] == 0:
                visited[x][y] = 1
                q.put([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
# AGC033 A-Darker and Darker
import queue
h,w = map(int,input().split())
visited=[[0]*w for _ in range(h)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i][j] = 1
            q.put([i,j,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        x,y = i+di,j+dj
        if (0<=x<h) and (0<=y<w):
            if visited[x][y] == 0:
                visited[x][y] = 1
                q.put([x,y,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
visited=[[0]*w for _ in range(h)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
a = []
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            visited[i][j] = 1
            q.put([i,j,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        if (0<=i+di<h) and (0<=j+dj<w):
            if visited[i+di][j+dj] == 0:
                visited[i+di][j+dj] = 1
                q.put([i+di,j+dj,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
visited = [[False] * w for _ in range(h)]

q = []
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            hp.heappush(q, (0, i, j))

while q:
    cnt, y, x = hp.heappop(q)
    for dy, dx in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
        ny, nx = dy + y, dx + x
        if ny < 0 or nx < 0 or ny >= h or nx >= w:
            continue
        if not visited[ny][nx] and a[ny][nx] == '.':
            visited[ny][nx] = True
            hp.heappush(q, (cnt + 1, ny, nx))

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
a = [list(input()) for _ in range(h)]
visited=[[0]*w for _ in range(h)]
q = queue.Queue()
t = ((1,0),(-1,0),(0,1),(0,-1))
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            visited[i][j] = 1
            q.put([i,j,0])
            
while not q.empty():
    i,j,cost = q.get()
    for di,dj in t:
        if (0<=i+di<h) and (0<=j+dj<w):
            if visited[i+di][j+dj] == 0:
                visited[i+di][j+dj] = 1
                q.put([i+di,j+dj,cost+1])
            
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import heapq as hp

h, w = map(int, input().split())
a = np.array([list(input()) for _ in range(h)])
a = np.pad(a, 1, 'constant')

q = []
for i in range(h+2):
    for j in range(w+2):
        if a[i][j] == '#':
            hp.heappush(q, (0, i, j))

while q:
    cnt, y, x = hp.heappop(q)
    for dy, dx in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
        ny, nx = dy + y, dx + x
        if a[ny][nx] == '.':
            hp.heappush(q, (cnt + 1, ny, nx))
            a[ny][nx] = '#'
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
    H, W = map(int,input().split())
    s = [list(map(str,input())) for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]
    
    q = deque([])
    for i in range(H):
        for j in range(W):
            if s[i][j] == "#":
                dist[i][j] = 0
                q.append((i, j))
    
    ans = 0
    while q:
        x, y = q.popleft()
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if (0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and s[nx][ny] == '.'):
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx, ny))
                ans = max(ans, dist[nx][ny])
                
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INF = -1
H, W = map(int,input().split())
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

q = deque()
for i in range(H):
    line = list(input())
    for j in range(W):
        if line[j] == '#':
            d[i][j] = 0
            q.append([i, j, 0])

ans = 0

while len(q) > 0:
    p = q.popleft()
    ans = max(ans, p[2])
    for i in range(4):
        nx = p[0] + tx[i]
        ny = p[1] + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and d[nx][ny] == INF:
            d[nx][ny] = p[2] + 1
            q.append([nx, ny, p[2]+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
import sys
input = sys.stdin.readline
INF = -1
H, W = map(int,input().split())
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

q = Queue()
for i in range(H):
    line = list(input())
    for j in range(W):
        if line[j] == '#':
            d[i][j] = 0
            q.put([i, j, 0])

ans = 0

while not q.empty():
    p = q.get()
    ans = max(ans, p[2])
    for i in range(4):
        nx = p[0] + tx[i]
        ny = p[1] + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and d[nx][ny] == INF:
            d[nx][ny] = p[2] + 1
            q.put([nx, ny, p[2]+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
INF = -1
H, W = map(int,input().split())
MAP = [list(input()) for _ in range(H)]
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

q = Queue()
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            d[i][j] = 0
            q.put([i, j, 0])

ans = 0

while not q.empty():
    p = q.get()
    ans = max(ans, p[2])
    for i in range(4):
        nx = p[0] + tx[i]
        ny = p[1] + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and d[nx][ny] == INF:
            d[nx][ny] = p[2] + 1
            q.put([nx, ny, p[2]+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
INF = 10 ** 8
H, W = map(int,input().split())
MAP = [list(input()) for _ in range(H)]
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]

q = Queue()
for i in range(H):
    for j in range(W):
        if MAP[i][j] == '#':
            d[i][j] = 0
            q.put([i, j, 0])

ans = 0

while not q.empty():
    p = q.get()
    ans = max(ans, p[2])
    for i in range(4):
        nx = p[0] + tx[i]
        ny = p[1] + ty[i]
        if 0 <= nx <= H-1 and 0 <= ny <= W-1 and d[nx][ny] == INF:
            d[nx][ny] = p[2] + 1
            q.put([nx, ny, p[2]+1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

H, W = LI()
A = []
for i in range(H):
    a = list(str(input()))
    A.append(a)
# 複数のスタート地点が存在してもqueに突っ込むことで同様の効果が得られる．
visited = [[-1 for i in range(W)] for j in range(H)]

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

moves = [[0,1],[1,0],[-1,0],[0,-1]]
cnt = 0
while len(d) > 0:
    X, Y = d.popleft()
    cnt = visited[X][Y]
    for x, y in moves:
        n_X = X + x
        n_Y = Y + y
        if 0 <= n_X < H and 0 <= n_Y< W:
            if visited[n_X][n_Y] == -1:
                visited[n_X][n_Y] = cnt + 1
                d.append((n_X, n_Y))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split(" "))
ar = []
br = []
for i in range(h):
    l = list(input())
    ar.append(l)
    for j in range(w):
        if l[j] == "#":
            br.append([i,j])
count = len(br)
ans = 0
k = 0
for r in br:
    if r[0] >= 1:
        if ar[r[0]-1][r[1]] == '.':
            ar[r[0]-1][r[1]] = "#"
            br.append([r[0]-1,r[1]])
            k += 1
    if r[1] < w-1:
        if ar[r[0]][r[1]+1] == '.':
            ar[r[0]][r[1]+1] = "#"
            br.append([r[0],r[1]+1])
            k += 1
    if r[0] < h-1:
        if ar[r[0]+1][r[1]] == '.':
            ar[r[0]+1][r[1]] = "#"
            br.append([r[0]+1,r[1]])
            k += 1
    if r[1] >= 1:
        if ar[r[0]][r[1]-1] == '.':
            ar[r[0]][r[1]-1] = "#"
            br.append([r[0],r[1]-1])
            k += 1
    count -= 1
    if count == 0:
        if k >= 1:
            ans += 1
            count = k
            k = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
l=[]
l.append('@'*(w+2))
for i in range(h):
    l.append('@'+input()+'@')
l.append('@'*(w+2))
q=deque()
p=[[-1 for i in j] for j in l]
for i in range(1,h+1):
    for j in range(1,w+1):
        if l[i][j]=='#':
            q.append([i,j])
            p[i][j]=0
while len(q)>0:
    x,y=q.popleft()
    for i,j in [[1,0],[-1,0],[0,-1],[0,1]]:
        if l[x+i][y+j]=='.' and p[x+i][y+j]==-1:
            q.append([x+i,y+j])
            p[x+i][y+j]=p[x][y]+1
a=0
for i in p:
    for j in i:
        a=max(a,j)
print(a)
#print(*p,sep='\n')