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: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
grid = [list(input()) + [False] for _ in range(H)]
grid = grid + [[False for _ in range(W + 1)]]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if grid[nx][ny] == '.':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)

Submission status: Accepted

Solution code:
from collections import deque
import copy

h,w = map(int, input().split())
s = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
q = deque([(i, j) for i in range(1,h+1) for j in range(1,w+1) if s[i][j] == "#"])
white = 0
while True:
  q2 = deque()
  while q:
    a,b = q.popleft()
    if s[a-1][b] == ".":
      s[a-1][b] = "#"
      q2.append((a-1,b))
    if s[a+1][b] == ".":
      s[a+1][b] = "#"
      q2.append((a+1,b))
    if s[a][b-1] == ".":
      s[a][b-1] = "#"
      q2.append((a,b-1))
    if s[a][b+1] == ".":
      s[a][b+1] = "#"
      q2.append((a,b+1))   
  if q2:
    q = copy.copy(q2)
    white += 1
  else:
    print(white)
    break

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())

gridgraph = [list(input()) for _ in range(H)]
q = deque()
visited = [[False]*W for _ in range(H)]
ans = [[1e+9]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if gridgraph[i][j] == "#":
            q.append((i, j))
            visited[i][j] = True
            ans[i][j] = 0
            
while len(q):
    cy, cx = q.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        if not (cy+dy >= 0 and H-1 >= cy+dy and cx+dx >= 0 and W-1 >= cx+dx):
            continue
        if visited[cy+dy][cx+dx]:
            continue
        visited[cy+dy][cx+dx] = True
        ans[cy+dy][cx+dx] = min(ans[cy+dy][cx+dx], ans[cy][cx]+1)
        q.append((cy+dy, cx+dx))

min_value = 0
for a in ans:
    min_value = max(min_value, max(a))
print(min_value)

Submission status: Accepted

Solution code:
def main():

    H, W = map(int, input().split())
    A = []
    white = 0
    h = []
    for i in range(H):
        A.append(list(input()))
        for j in range(W):
            if A[i][j] == '#':
                h.append([i, j])
            else:
                white += 1

    cnt = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while h and white > 0:
        temp = []
        cnt += 1
        for i, j in h:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0<=i1<H and 0<=j1<W and A[i1][j1] == '.':
                    temp.append([i1, j1])
                    A[i1][j1] = '#'
                    white -= 1
        h = temp
    return cnt

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
from collections import deque
if sys.platform =='win32':
  sys.stdin=open('./input.txt')
input = sys.stdin.readline
def MAP(): return [int(x) for x in input().split()]

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

H, W = [int(s) for s in input().split()]

M = []

for i in range(H):
	M.append([s for s in input().rstrip()]) 

syx = []
for i in range(H):
	for j in range(W):
		if M[i][j] == '#': syx.append([i,j])
# print(syx)

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

for s in syx:
	dist[s[0]][s[1]] = 0

queue.append(syx)

while queue:
	nodelist = queue.popleft()
	# print(nodelist)
	nextnode = []

	for node in nodelist:
		y, x = node
		# print(y,x)
		
		for i in range(4):
			ny = y+dy[i]
			nx = x+dx[i]
			# print(ny, nx)
			
			if ny>=H or ny<0 or nx>=W or nx<0:
				continue
			if dist[ny][nx] != -1:
				continue
			
			if M[ny][nx] == '.':
				dist[ny][nx] = dist[y][x]+1
				nextnode.append([ny,nx])

	# print(nextnode)
	if len(nextnode)!=0:
		queue.append(nextnode)

ans = 0
for d in dist:
  ans = max(ans, max(d))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
d=[]
for i in range(H):    
    d.append([0 if c=='#' else -1 for c in input()])
#print(d)
q=deque()
for i in range(H):
    for j in range(W):
        if not d[i][j]:
            q.append((i,j))
#print(q)
while q:
    u=q.popleft()
    ui,uj=u
    for v in [(ui-1,uj),(ui+1,uj),(ui,uj-1),(ui,uj+1)]:
        vi,vj=v
        if 0<=vi<=H-1 and 0<=vj<=W-1 and d[vi][vj]==-1:
            d[vi][vj]=d[ui][uj]+1
            q.append(v)
#print(d)
print(max(max(di) for di in d))

Submission status: Accepted

Solution code:
from collections import deque

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

q = []
for y in range(H) :
    for x in range(W) :
        if A[y][x] == '#' :
            q.append((y, x))

ret = 0
while True :
    r = []
    while q :
        cy, cx = q.pop()
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < H and 0 <= nx < W and A[ny][nx] == '.' :
                A[ny][nx] = '#'
                r.append((ny, nx))
    ret += 1
    if len(r) == 0 :
        break
    
    q = r
    
print(ret - 1)

Submission status: Accepted

Solution code:

import sys
from collections import deque

# input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def main():
    BLACK = '#'
    WHITE = '.'
    H, W = map(int, input().split())
    graph = [None] * H
    # w_score = [[0 for i in range(W)] for i in range(H)]
    # h_score = [[0 for i in range(W)] for i in range(H)]
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    visited = [[False for i in range(W)] for i in range(H)]
    initial = []

    for i in range(H):
        graph[i] = list(input())

        for j in range(W):
            if graph[i][j] == BLACK:
                initial.append((i, j))
                visited[i][j] = True

    # print(visited)
    # print(graph)

    q = deque()
    q.append(initial)
    ans = 0
    while len(q) != 0:
        n = q.popleft()
        # print(ans, n)

        items = set()
        for p in n:
            for d in options:
                i = p[0] + d[0]
                j = p[1] + d[1]

                if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] == WHITE:
                    visited[i][j] = True
                    graph[i][j] = BLACK
                    items.add((i, j))
                # else:
                #     print(i, j)

        if len(items) > 0:
            ans += 1
            q.append(items)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

#####################################


#1:43
h,w = list(map(int, input().split()))
queue=[]
mp=[[-1 for i in range(h)]for j in range(w)]
for i in range(h):
    temp = input()
    for j in range(len(temp)):
        if(temp[j]=='#'):
            queue.append([j,i,0])
            mp[j][i]=0
            
nowq = 0
while(True):
    x,y,times = queue[nowq]
    if(mp[min(x+1,w-1)][y]==-1):
        mp[min(x+1,w-1)][y]=times+1
        queue.append([x+1,y,times+1])
    if(mp[max(x-1,0)][y]==-1):
        mp[max(x-1,0)][y]=times+1
        queue.append([x-1,y,times+1])
    if(mp[x][min(y+1,h-1)]==-1):
        mp[x][min(y+1,h-1)]=times+1
        queue.append([x,y+1,times+1])
    if(mp[x][max(y-1,0)]==-1):
        mp[x][max(y-1,0)]=times+1
        queue.append([x,y-1,times+1])
    nowq+=1
    if(len(queue)==nowq):
        break
ans=0
for i in range(w):
    ans=max(ans,max(mp[i]))
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    fq = [[True] * w for _ in range(h)]
    ql = collections.deque()
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                fq[i][j] = False
                ql.append([0, i, j])
    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if fq[xv][yv]:
                        ql.append([cost + 1, xv, yv])
                        fq[xv][yv] = False
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
q=deque()
l=[]
for i in range(h):
  l.append(list(input()))
lb=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
  for j in range(w):
    if l[i][j]=="#":
      q.append([i,j])
move=[[1,0],[-1,0],[0,1],[0,-1]]
count=0
b=True
q2=deque()
while b:
  while q:
    q1=q.popleft()
    x1=q1[0]
    y1=q1[1]
    for i in range(4):
      dx=move[i][0]
      dy=move[i][1]
      x=x1+dx
      y=y1+dy
      if x<0 or x>h-1 or y<0 or y>w-1:
        pass
      elif l[x][y]=="#":
        pass
      else:
        l[x][y]="#"
        q2.append([x,y])
  if len(q2)!=0:
    q=q2
    q2=deque()
    count+=1
  else:
    b=False
print(count)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
cnt = [[float('inf')]*w for _ in range(h)]
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))
q = deque([])
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      cnt[i][j] = 0 

def bfs():
  while q:
    y, x = q.popleft()
    for dy, dx in moves:
      ny = y + dy
      nx = x + dx 
      if 0 <= ny < h and 0 <= nx < w and a[ny][nx] == '.' and used[ny][nx] == 0:
        used[ny][nx] = 1
        cnt[ny][nx] = min(cnt[ny][nx], cnt[y][x]+1)
        q.append([ny, nx])

used = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if a[i][j] == '#':
      used[i][j] = 1
      q.append([i, j])

bfs()

ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, cnt[i][j])
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                ql.append([0, i, j])

    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        a[xv][yv] = "#"
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    for i in range(h):
        s = str(readline().rstrip().decode('utf-8'))
        for j in range(w):
            if s[j] == "#":
                a[i][j] = False
                ql.append([0, i, j])

    mt = 0
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv]:
                        ql.append([cost + 1, xv, yv])
                        a[xv][yv] = False
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = collections.deque()
    for i in range(h):
        s = list(str(readline().rstrip().decode('utf-8')))
        for j in range(w):
            if s[j] == "#":
                ql.append([0, i, j])
                a[i][j] = False
    while ql:
        cost, x, y = ql.popleft()
        for xv, yv in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if 0 <= xv < h and 0 <= yv < w:
                if a[xv][yv]:
                    ql.append([cost + 1, xv, yv])
                    a[xv][yv] = False
    print(cost)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
import copy

def main():
    h,w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y,x = que.popleft()
            if x >0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x <w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y >0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
        if nque:
            que = copy.copy(nque)
        else:
            break
    print(count-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()  # 黒いセルの座標
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

Submission status: Accepted

Solution code:
from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

d = 0
while black_cells:
    # キューとして使うのでpop()ではなくpopleft()
    h, w = black_cells.popleft()  # 黒いセルの座標
    d = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
            dist[new_h][new_w] = d+1
            black_cells.append((new_h, new_w))

print(d)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int, input().split())
A = []
for _ in range(H):
    temp = list(input())
    A.append(temp)
ans = 0
Q = deque([])
break_loop = 1
def bfs(x,y):
    global break_loop
    next_ = [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
    for i in next_:
        if 0 <= i[0] <= H-1 and 0 <= i[1] <= W-1 and A[i[0]][i[1]] == ".":
            break_loop = 0
            A[i[0]][i[1]] = "#"
            Q.append([i[0],i[1]])

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

while len(Q) > 0:
    break_loop = 1
    for _ in range(len(Q)):
        Q_next = Q.popleft()
        bfs(Q_next[0],Q_next[1])
    if break_loop:
        break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a1 = [[5000] * (w+2) for i in range(h+2)]
a2 = [['.'] * (w+2) for i in range(h+2)]
for i in range(h):
  a2[i+1][1:-1] = list(input())
for i in range(h):
  for j in range(w):
    if a2[i+1][j+1] == '#':
      a1[i+1][j+1] = 0
for i in range(w):
  for j in range(h):
    a1[j+1][i+1] = min(a1[j][i+1]+1,a1[j+1][i+1])
for i in range(w):
  for j in range(h):
    a1[h-j][i+1] = min(a1[h-j+1][i+1]+1,a1[h-j][i+1])
for i in range(h):
  for j in range(w):
    a1[i+1][j+1] = min(a1[i+1][j]+1,a1[i+1][j+1])
for i in range(h):
  for j in range(w):
    a1[i+1][w-j] = min(a1[i+1][w-j+1]+1,a1[i+1][w-j])
m = 0
for i in range(h):
  for j in range(w):
    m = max(m,a1[i+1][j+1])
print(m)

Submission status: Accepted

Solution code:
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2)
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

#enumerate input

def main():
    h,w=map(int,input().split())
    stack=deque()
    grid=[["#"]*(w+2)]
    for i in range(h):
        tmp=[]
        for k,v in enumerate(input()):
            if v=="#":
                tmp.append("#")
                stack.appendleft((i+1,k+1))
            else:
                tmp.append(v)
        grid.append(["#"]+tmp+["#"])
    grid.append(["#"]*(w+2))
#    for i in grid:
#        print(*i)
    for i in range(h*w):
        tmp=deque()
        while stack:
            y,x=stack.pop()
            for my,mx in ((0,1),(1,0),(-1,0),(0,-1)):
                if grid[y+my][x+mx]==".":
                    grid[y+my][x+mx]="#"
                    tmp.appendleft((y+my,x+mx))
        stack=tmp
        if not len(stack):
            print(i)
            exit()
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
INF = 1001001001
dist = [[INF for _ in range(w)] for _ in range(h)]

d = deque()
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            d.append([i, j])
            dist[i][j] = 0
ans = 0
while(d):
    y,x = d.popleft()
    difflist = [[1,0], [0,1], [-1, 0], [0, -1]]
    for dy, dx in difflist:
        y2 = y + dy
        x2 = x + dx
        if 0 <= y2 < h and 0 <= x2 < w and dist[y2][x2]>(dist[y][x] + 1):
            d.append([y2, x2])
            dist[y2][x2] = dist[y][x] + 1
            ans = max(ans, dist[y2][x2])

print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
from collections import deque
d=deque()
c=[[0]*w for _ in range(h)]
for i in range(1,h+1):
  for j in range(1,w+1):
    if a[i][j]=='#':
      d.append([i,j])
di=[[0,1],[1,0],[-1,0],[0,-1]]
while d:
  g=d.popleft()
  for i in di:
    x=g[0]+i[0]
    y=g[1]+i[1]
    if a[x][y]=='.':
      if c[x-1][y-1]==0:
        d.append([x,y])
        c[x-1][y-1]=c[g[0]-1][g[1]-1]+1
m=0
for i in range(h):
  for j in range(w):
    m=max(m,c[i][j])
print(m)

Submission status: Accepted

Solution code:
from collections import deque
 
h, w = map(int, input().split())
s = [input() for i in range(h)]
 
d = [[h+w for j in range(w)] for i in range(h)]
que = deque()
 
#黒だったらスタートキューに入れる
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
        que.append((i, j))
        d[i][j] = 0
 
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
 
 
while que:
    p = que.popleft()
    # 黒にする4方向をループ
    for i in range(4):
        nx = p[1] + dx[i]
        ny = p[0] + dy[i]
 
        if (0<=nx<w) and (0<=ny<h) and (d[ny][nx]==h+w):
            que.append((ny, nx))
            d[ny][nx] = d[p[0]][p[1]] + 1
 
res = max(map(max, d))
print(res)

Submission status: Accepted

Solution code:
from collections import deque

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

d = [[10**6]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            d[i][j] = 0
            q.append((i, j, 0))
            
while q:
    temp = q.popleft()
    y = temp[0]
    x = temp[1]
    r = temp[2]
    if y != 0:
        if d[y-1][x] > r+1 and A[y-1][x] == ".":
            d[y-1][x] = r+1
            q.append((y-1, x, r+1))
    if y != H-1:
        if d[y+1][x] > r+1 and A[y+1][x] == ".":
            d[y+1][x] = r+1
            q.append((y+1, x, r+1))
    if x != 0:
        if d[y][x-1] > r+1 and A[y][x-1] == ".":
            d[y][x-1] = r+1
            q.append((y, x-1, r+1))
    if x != W-1:
        if d[y][x+1] > r+1 and A[y][x+1] == ".":
            d[y][x+1] = r+1
            q.append((y, x+1, r+1))
                        
ans = 0
for i in range(H):
    ans = max(ans, max(d[i]))
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    h,w = map(int,input().split())
    a=[]
    que=[]
    for _ in range(h):
        a.append(list(input()))
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                que.append([i,j])
                a[i][j]=0
    ans=0
    while que!=[]:
        tank=[]
        for i,j in que:
            if j<w-1 and a[i][j+1]==".":
                tank.append([i,j+1])
                a[i][j+1]=a[i][j]+1
            if 0<j and a[i][j-1]==".":
                tank.append([i,j-1])
                a[i][j-1]=a[i][j]+1
            if i<h-1 and a[i+1][j]==".":
                tank.append([i+1,j])
                a[i+1][j]=a[i][j]+1
            if 0<i and a[i-1][j]==".":
                tank.append([i-1,j])
                a[i-1][j]=a[i][j]+1
        que=tank
        ans+=1
    print(ans-1)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#editorial 参照
#一度見た黒マスはその隣を見なくてよいので幅優先探索でよい

from collections import deque

h,w = map(int, input().split( ))
a = []
for _ in range(h):
    a_ = input()
    A =[]
    for i in range(w):
        A.append(a_[i])
    a.append(A)

cnt = [[-1]*w for _ in range(h)]

Q = deque()

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

while Q:
    i,j = Q.popleft()
    for (k,l) in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0<=i+k and 0<=j+l and i+k<=h-1 and j+l<=w-1:
            if a[i+k][j+l]==".":
                a[i+k][j+l] ="#"
                cnt[i+k][j+l]=cnt[i][j]+1
                Q.append((i+k,j+l))
ans = 0
for i in range(h):
    ans = max(ans,max(cnt[i]))


print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    h, w = map(int, input().split())
    G = [["#"]*(w+2)]+[["#"]+list(input())+["#"] for i in range(h)]+[["#"]*(w+2)]
    dy, dx = [-1, 1, 0, 0], [0, 0, -1, 1]
    dist = [[-1 for j in range(w+2)] for i in range(h+2)]
    que = deque()
    
    for i in range(1, h+1):
        for j in range(1, w+1):
            if G[i][j] == "#":
                dist[i][j] = 0
                que.append((i, j))
    
    while (len(que) != 0):
        y, x = que[0][0], que[0][1]
        que.popleft()

        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if G[ny][nx] == "#":
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                que.append((ny, nx))
    
    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            ans = max(ans, dist[i][j])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
line = sys.stdin.readline

H, W = map(int, line().split())
grid = np.full((H + 2, W + 2), 1000)
grid[1:-1, 1:-1] = (np.array([list(line().rstrip()) for _ in range(H)]).reshape(H, W) == '#') * 1
grid2 = grid.copy()
grid2[1:-1, 1:-1] = np.where(grid2[1:-1, 1:-1] < 1, 1, 0)

down = grid.copy()
for i in range(1, H + 1):
    down[i, 1:-1] = (down[i - 1, 1:-1] * grid2[i - 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

up = grid.copy()
for i in range(H, 0, -1):
    up[i, 1:-1] = (up[i + 1, 1:-1] * grid2[i + 1, 1:-1] + grid2[i, 1:-1]) * grid2[i, 1:-1]

right = grid.copy()
for i in range(1, W + 1):
    right[1:-1, i] = (right[1:-1, i - 1] * grid2[1:-1, i - 1] + grid2[1:-1, i]) * grid2[1:-1, i]

left = grid.copy()
for i in range(W, 0, -1):
    left[1:-1, i] = (left[1:-1, i + 1] * grid2[1:-1, i + 1] + grid2[1:-1, i]) * grid2[1:-1, i]

v = np.minimum(down, up)
h = np.minimum(left, right)

answer = np.minimum(v, h)
for i in range(1, H):
    answer[i + 1] = np.minimum(answer[i] + 1, answer[i + 1])
for i in range(H, 0, -1):
    answer[i - 1] = np.minimum(answer[i] + 1, answer[i - 1])
print(int(answer[1:-1, 1:-1].max()))

Submission status: Accepted

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

state = []
# 初期状態
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            state.append([w, h])

tmp = []
ret = 0
while len(state) > 0:
    tmp = list()
    ret += 1
    for x, y in state:
        for nx, ny in ((1,0), (-1,0), (0,1), (0,-1)):
            nx += x
            ny += y
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue

            if field[ny][nx] == ".":
                field[ny][nx] = "#"
                tmp.append([nx, ny])
    state = tmp

print(ret-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
INF = 10**9
sheet = []
log = [[True]*W for i in range(H)]
step = [(-1,0),(1,0),(0,-1),(0,1)]
stuck = deque()
ans = 0

for i in range(H):
  line = input()
  for j in range(W):
    if line[j]=='#':
      stuck += [(i,j,0)]
      log[i][j] = False
      
while stuck:
  y, x, m = stuck.popleft()
  for s in step:
    dx, dy = s
    if x+dx<0 or x+dx>W-1 or y+dy<0 or y+dy>H-1:
      continue
    if log[y+dy][x+dx]:
      log[y+dy][x+dx]=False
      stuck += [(y+dy, x+dx, m+1)]
      if ans<m+1:
        ans = m+1
      
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H , W = map(int,input().split())
A = []
start = []
for i in range(H):
    row = list(input())
    for j in range(W):
        if row[j] == "#":
            start.append([i , j])
    A.append(row)

def bfs(s):
    score = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque()
    for y , x in s:
        score[y][x] = 0
        q.append([y,x])
    diff = [[0,1],[1,0],[-1,0],[0,-1]]

    while q:
        now_y , now_x = q.popleft()
        for dy , dx in diff:
            next_y , next_x = now_y + dy , now_x + dx
            if 0 <= next_y and next_y < H and 0 <= next_x and next_x < W and score[next_y][next_x] == -1:
                score[next_y][next_x] = score[now_y][now_x] + 1
                q.append([next_y,next_x])
    ret_val = 0
    for i in range(H):
        for j in range(W):
            ret_val = max(ret_val , score[i][j])
    return ret_val


print(bfs(start))

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
ans=0
field=[["*" for i in range(w+2)]]+[["*"]+list(input())+["*"] for i in range(h)]+[["*" for i in range(w+2)]]
queue=deque([])
for H in range(h+2):
    for W in range(w+2):
        if field[H][W]=="#":
            queue.append((H,W))
            field[H][W]=0
        elif field[H][W]==".":
          field[H][W]=-1
move=[(0,1),(0,-1),(1,0),(-1,0)]
ans=0
while queue:
    pos=queue.popleft()
    for i in move:
      if field[pos[0]+i[0]][pos[1]+i[1]]!=-1:continue
      if field[pos[0]+i[0]][pos[1]+i[1]]=="*":continue
      field[pos[0]+i[0]][pos[1]+i[1]]=field[pos[0]][pos[1]]+1
      queue.append((pos[0]+i[0],pos[1]+i[1]))
      if ans < field[pos[0]+i[0]][pos[1]+i[1]]:ans=field[pos[0]+i[0]][pos[1]+i[1]]
print(ans)