Problem:


Score : 700 points

Problem Statement

Takahashi is locked within a building.

This building consists of H×W rooms, arranged in H rows and W columns.
We will denote the room at the i-th row and j-th column as (i,j). The state of this room is represented by a character A_{i,j}. If A_{i,j}= #, the room is locked and cannot be entered; if A_{i,j}= ., the room is not locked and can be freely entered.
Takahashi is currently at the room where A_{i,j}= S, which can also be freely entered.

Each room in the 1-st row, 1-st column, H-th row or W-th column, has an exit.
Each of the other rooms (i,j) is connected to four rooms: (i-1,j), (i+1,j), (i,j-1) and (i,j+1).

Takahashi will use his magic to get out of the building. In one cast, he can do the following:

Move to an adjacent room at most K times, possibly zero. Here, locked rooms cannot be entered.

Then, select and unlock at most K locked rooms, possibly zero. Those rooms will remain unlocked from then on.

His objective is to reach a room with an exit. Find the minimum necessary number of casts to do so.

It is guaranteed that Takahashi is initially at a room without an exit.

Constraints

3 ≤ H ≤ 800

3 ≤ W ≤ 800

1 ≤ K ≤ H×W

Each A_{i,j} is # , .  or S.

There uniquely exists (i,j) such that A_{i,j}= S, and it satisfies 2 ≤ i ≤ H-1 and 2 ≤ j ≤ W-1.

Input

Input is given from Standard Input in the following format:

H W K
A_{1,1}A_{1,2}...A_{1,W}
:
A_{H,1}A_{H,2}...A_{H,W}

Output

Print the minimum necessary number of casts.

Sample Input 1

3 3 3
#.#
#S.
###

Sample Output 1

1

Takahashi can move to room (1,2) in one cast.

Sample Input 2

3 3 3
###
#S#
###

Sample Output 2

2

Takahashi cannot move in the first cast, but can unlock room (1,2).
Then, he can move to room (1,2) in the next cast, achieving the objective in two casts.

Sample Input 3

7 7 2
#######
#######
##...##
###S###
##.#.##
###.###
#######

Sample Output 3

2



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


Sample output:
1

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(A, H, W, K, S):
    INF = 10**9
    dist = np.full(H * W, INF, np.int32)
    q = np.empty(H * W + 100, np.int32)
    q[:2] = 2, 2

    def push(q, x):
        q[q[1]] = x
        q[1] += 1

    def pop(q):
        q[0] += 1
        return q[q[0] - 1]

    def is_empty(q):
        return q[0] == q[1]

    move = (1, -1, W, -W)
    dist[S] = 0
    push(q, S)
    while not is_empty(q):
        v = pop(q)
        for d in (1, -1, W, -W):
            w = v + d
            if A[w] == '#' or dist[w] <= dist[v] + 1:
                continue
            dist[w] = dist[v] + 1
            push(q, w)
    dist = dist.reshape(H, W)
    min_d = INF
    for h in range(1, H - 1):
        for w in range(1, W - 1):
            if dist[h, w] > K:
                continue
            d = min(h - 1, H - 2 - h, w - 1, W - 2 - w)
            min_d = min(d, min_d)
    return 1 + (min_d + K - 1) // K

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    u1 = numba.from_dtype(np.dtype('U1'))
    signature = (u1[:], i8, i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

H, W, K = map(int, readline().split())
A = np.full((H + 2, W + 2), '#', 'U1')
A[1:-1, 1:-1] = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

H, W = A.shape
A = A.ravel()
S = np.where(A == 'S')[0][0]

print(main(A, H, W, K, S))

Submission status: Accepted

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

H, W, K = map(int, readline().split())

G = [[2]*(W+2)]

st = (None, None)
for h in range(H):
    g = readline().strip()
    if 'S' in g:
        st = (1+h, 1+g.index('S'))
    
    G.append([2] + [1 if s == '#' else 0 for s in g] + [2])

G.append([2]*(W+2))

DIREC = [(0, -1), (0, 1), (1, 0), (-1, 0)]

Q = deque([st])
INF = 10**9+7
dist = [[INF]*(W+2) for _ in range(H+2)]
for h, w in Q:
    dist[h][w] = 0


Q2 = deque([st])
ans = INF
while Q:
    nh, nw = Q.pop()
    for dh, dw in DIREC:
        fh, fw = nh+dh, nw+dw
        if G[fh][fw]:
            continue
        if dist[fh][fw] > 1 + dist[nh][nw]:
            dist[fh][fw] = 1 + dist[nh][nw]
            if dist[fh][fw] <= K:
                Q2.append((fh, fw))
                if fh == 1 or fh == H or fw == 1 or fw == W:
                    ans = 1
            Q.appendleft((fh, fw))

if ans == INF:
    dist = [[INF]*(W+2) for _ in range(H+2)]
    for h, w in Q2:
        dist[h][w] = 0
    while Q2:
        nh, nw = Q2.pop()
        for dh, dw in DIREC:
            fh, fw = nh+dh, nw+dw
            if G[fh][fw] == 2:
                continue
            if dist[fh][fw] > 1 + dist[nh][nw]:
                dist[fh][fw] = 1 + dist[nh][nw]
                if fh == 1 or fh == H or fw == 1 or fw == W:
                    ans = min(ans, 2+(dist[fh][fw]-1)//K)
                Q2.appendleft((fh, fw))

print(ans)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    a = [input() for _ in range(h)]
    for i,ai in enumerate(a):
        if "S" in ai:
            si = i
            sj = ai.find("S")
            break
    q = queue.Queue()
    t = [[10**10]*w for _ in [0]*h]
    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    t[si][sj] = 0
    q.put((si,sj))
    g1 = [(si,sj)]
    while not q.empty():
        qi,qj = q.get()
        for di,dj in dir:
            if 0 <= qi+di <= h-1 and 0 <= qj+dj <= w-1 and a[qi+di][qj+dj] == ".":
                if t[qi+di][qj+dj] > t[qi][qj] + 1:
                    t[qi+di][qj+dj] = t[qi][qj] + 1
                    g1.append((qi+di,qj+dj))
                    if t[qi][qj] != k-1:
                        q.put((qi+di,qj+dj))

    mi = 10**4
    for i,j in g1:
        if mi > (i+k-1)//k+1:
            mi = (i+k-1)//k+1
        if mi > (j+k-1)//k+1:
            mi = (j+k-1)//k+1
        if mi > (h-1-i+k-1)//k+1:
            mi = (h-1-i+k-1)//k+1
        if mi > (w-1-j+k-1)//k+1:
            mi = (w-1-j+k-1)//k+1
    print(mi)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

h,w,k=map(int,input().split())
a=[ [c for c in input()] for _ in range(h)]

s=False
for i in range(h):
    for j in range(w):
        if a[i][j]=="S":
            s=(i,j)
            break
    if s:
        break
min_dis=w*h
dq=collections.deque()
dq.append((0,s[0],s[1]))

moved=[[False for _ in  range(w)] for _ in range(h)]
while dq:
    m,y,x=dq.popleft()
    if moved[y][x]:
        continue
    else:
        moved[y][x]=True
    if m>k:
        continue
    if y==0 or y==h-1 or x==0 or x==w-1:
        print(1)
        exit()
    min_dis=min(min_dis, y, h-1-y, x, w-x-1)
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<=y+dy<h and 0<=x+dx<w and a[y+dy][x+dx] == '.' and not moved[y+dy][x+dx]:
            dq.append((m+1, y+dy, x+dx))
print(1+(min_dis+k-1)//k)

Submission status: Accepted

Solution code:

h,w,k=map(int,input().split())
maze=[]

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
ans=float("INF")
l=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p={(x,y)}
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.add((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

for x,y in p:
    ans=min(ans,(min(x,y,h-1-x,w-1-y)+k-1)//k+1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w,k = map(int,input().split())
A = []
ans = 10**10
for i in range(h):
    A.append(input())
    for j in range(w):
        if A[i][j] == 'S':
            start = (i,j)
d = [[10**10]*w for _ in range(h)]
d[start[0]][start[1]] = 0
que = deque([start])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
while que:
    px,py = que.popleft()
    ans = min(ans, 2 + (min(px,py,h-px-1,w-py-1)-1)//k)
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == '.' and d[nx][ny] == 10**10:
            d[nx][ny] = d[px][py] + 1
            if d[nx][ny] <= k:
                que.append((nx,ny))
print(ans)

Submission status: Accepted

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

H, W, K = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
si = sj = -1
for i in range(H):
    for j in range(W):
        if A[i][j] == 'S':
            si, sj = i, j
            break
    if si != -1:
        break
# ans = (min(si, H - si - 1, sj, W - sj - 1) + K - 1) // K
queue = deque([(si, sj)])
INF = 10**18
dist = [[INF] * W for _ in range(H)]
dist[si][sj] = 0
ans = INF
while queue:
    i, j = queue.popleft()
    ans = min(ans, 1 + (min(i, H - i - 1, j, W - j - 1) + K - 1) // K)
    if dist[i][j] == K:
        continue
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == '.' and dist[ni][nj] == INF:
            dist[ni][nj] = dist[i][j] + 1
            queue.append((ni, nj))
print(ans)

Submission status: Accepted

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

def main():
  h, w, k = map(int, input().split())
  A = [input().rstrip() for _ in range(h)]
  for i, a in enumerate(A):
    if "S" in a:
      sy = i
      sx = a.index("S")
      break

  que = deque()
  D = ((-1, 0), (0, -1), (1, 0), (0, 1))

  def bfs(y, x):
    seen = [0]*h
    seen[y] |= 1 << x
    F = deque()
    F.append((y, x, 0))
    while F:
      ny, nx, cnt = F.popleft()
      que.append((ny, nx, k))
      if cnt == k:
        continue
      for dy, dx in D:
        yy, xx = ny+dy, nx+dx
        if 0 <= yy < h and 0 <= xx < w:
          if A[yy][xx] == "#":
            continue
          if seen[yy] >> xx & 1:
            continue
          seen[yy] |= 1 << xx
          F.append((yy, xx, cnt+1))

  bfs(sy, sx)

  seen = [0]*h
  while que:
    y, x, cnt = que.popleft()
    if y == 0 or y == h-1 or x == 0 or x == w-1:
      ans = -(-cnt // k)
      break
    for dy, dx in D:
      ny, nx = y+dy, x+dx
      if 0 <= ny < h and 0 <= nx < w:
        if seen[ny] >> nx & 1:
          continue
        seen[ny] |= 1 << nx
        que.append((ny, nx, cnt+1))

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

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

h, w, k = map(int, input().split())
A = [input().rstrip() for _ in range(h)]
for i, a in enumerate(A):
  if "S" in a:
    sy = i
    sx = a.index("S")
    break

que = deque()
D = ((-1, 0), (0, -1), (1, 0), (0, 1))
        
def bfs(y, x):
  seen = [0]*h
  seen[y] |= 1 << x
  F = deque()
  F.append((y, x, 0))
  while F:
    ny, nx, cnt = F.popleft()
    que.append((ny, nx, k))
    if cnt == k:
      continue
    for dy, dx in D:
      yy, xx = ny+dy, nx+dx
      if 0 <= yy < h and 0 <= xx < w:
        if A[yy][xx] == "#":
          continue
        if seen[yy] >> xx & 1:
          continue
        seen[yy] |= 1 << xx
        F.append((yy, xx, cnt+1))

bfs(sy, sx)

seen = [0]*h
while que:
  y, x, cnt = que.popleft()
  if y == 0 or y == h-1 or x == 0 or x == w-1:
    ans = -(-cnt // k)
    break
  for dy, dx in D:
    ny, nx = y+dy, x+dx
    if 0 <= ny < h and 0 <= nx < w:
      if seen[ny] >> nx & 1:
        continue
      seen[ny] |= 1 << nx
      que.append((ny, nx, cnt+1))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

for i in range(H):
    for j in range(W):
        if A[i][j]=="S":
            s=(i,j)

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=deque([(0,s[0],s[1])])
while que:
    count,posx,posy=que.popleft()
    if count==K:
        continue

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            que.append((count+1,nx,ny))


ans=float("inf")
for x,y in start:
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
A=[input() for i in range(H)]
for i,l in enumerate(A):
    if 'S' in l:
        S=(K,i,l.index('S'))
from collections import deque
q=deque([S])
X=[(S[1],S[2])]
n=((0,1),(0,-1),(1,0),(-1,0))
v=[[0]*W for i in range(H)]
v[S[1]][S[2]]=1
while q:
    m,i,j=q.popleft()
    for x,y in n:
        if 0<=i+x<H and 0<=j+y<W:
            if v[i+x][j+y]:continue
            v[i+x][j+y]=1
            if A[i+x][j+y]=='.' and m>0:
                q.append((m-1,i+x,j+y))
                X.append((i+x,j+y))
print(min([min(0--i//K,0--(H-i-1)//K,0--j//K,0--(W-j-1)//K) for i,j in X])+1)

Submission status: Accepted

Solution code:
from collections import deque
import math

#入力
h,w,k=map(int,input().split())
a=[input() for i in range(h)]

#Sの位置の捜索
for i in range(h):
    for j in range(w):
        if a[i][j]=='S':
            sy,sx=i,j

#各種パラメータの初期設定
d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
    dist.append([inf]*w)
dist[sy][sx]=0

#一回目の魔法で移動できる範囲を幅優先探索
while len(d)!=0:
    b=d.popleft()
    p,q=b[0],b[1]
    for i in [[1,0],[0,-1],[-1,0],[0,1]]:
        by,bx=b[0]+i[0],b[1]+i[1]
        if bx>=0 and bx<w and by>=0 and by<h and a[by][bx]!='#' and dist[by][bx]==-1 and dist[p][q]<k:
            #訪問先が配列内かつ壁でなく未訪問、訪問元の距離がk以下のとき訪問
            d.append([by,bx])
            dist[by][bx]=dist[p][q]+1

#一回目で移動できる各地点からの魔法の使用回数を計算
for i in range(h):
    for j in range(w):
        if dist[i][j]!=-1:
            m=min(m,0--min(i,h-1-i,j,w-1-j)//k)

print(m+1)

Submission status: Accepted

Solution code:
from collections import deque
import math

#入力
h,w,k=map(int,input().split())
a=[input() for i in range(h)]

for i in range(h):
  for j in range(w):
    if a[i][j]=='S':
      sy,sx=i,j

d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
  dist.append([inf]*w)
dist[sy][sx]=0

while len(d)!=0:
  b=d.popleft()
  p,q=b[0],b[1]
  for i in [[1,0],[0,-1],[-1,0],[0,1]]:
    by,bx=b[0]+i[0],b[1]+i[1]
    if bx>=0 and bx<w and by>=0 and by<h:
      if a[by][bx]!='#' and dist[by][bx]==-1:
        d.append([by,bx])
        dist[by][bx]=dist[p][q]+1

for i in range(h):
  for j in range(w):
    if dist[i][j]!=-1 and dist[i][j]<=k:
      m=min(m,0--min(i,h-1-i,j,w-1-j)//k)

print(m+1)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H,W,K=map(int, input().split())
    A=[list(input()) for _ in range(H)]

    from collections import deque
    q=deque()
    for i in range(H):
        for j in range(W):
            if A[i][j]=='S':
                q.append((i,j,0))
                A[i][j]='#'

    ans=10**9
    while q:
        i,j,d = q.popleft()
        if i==0 or i==H-1 or j==0 or j==W-1:
            print(1)
            exit()
        ans = min(ans, (min(i,j,H-1-i,W-1-j) + K-1) // K + 1)
        if d==K: continue
        for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
            ni,nj=i+di,j+dj
            if A[ni][nj]!='#':
                q.append((ni,nj,d+1))
                A[ni][nj]='#'
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
b=[list("#"*(w+2))]+[list("#"+input()+"#")for _ in range(h)]+[list("#"*(w+2))]
for i in range(h+2):
  for j in range(w+2):
    if b[i][j]=="S":
      Q=[(i,j)]
      ans=0--min(i-1,h-i,j-1,w-j)//k
co=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while Q and co!=k+1:
  co+=1
  P=[]
  for i,j in Q:
    ans=min(ans,0--min(i-1,h-i,j-1,w-j)//k)
    for x,y in zip(dx,dy):
      if b[i+x][j+y]==".":
        b[i+x][j+y]=0
        P.append((i+x,j+y))
        if i+x in [1,h] or j+y in [1,w]:print(1);exit()
  Q=P
print(ans+1)

Submission status: Accepted

Solution code:
def main():
    from collections import deque

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

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

    G = [list(input()) for _ in range(H)]
    check = [[-1] * (W) for _ in range(H)]

    que = deque()

    flag = False
    for h in range(H):
        for w in range(W):
            if G[h][w] == 'S':
                que.append((h, w))
                flag = True
                break
        if flag:
            break

    x_min = h
    x_max = h

    y_min = w
    y_max = w

    check[h][w] = 0
    while que:
        tmp = que.popleft()
        
        x = tmp[0]
        y = tmp[1]
        
        now_ = check[x][y]
        if now_ == K:
            continue

        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if G[nx][ny] == '#':
                continue
            if check[nx][ny] == -1:
                check[nx][ny] = now_ + 1
                que.append((nx, ny))
                
                x_min = min(x_min, nx)
                x_max = max(x_max, nx)

                y_min = min(y_min, ny)
                y_max = max(y_max, ny)

    ans = 10 ** 18
    ans = min(ans, (x_min + K - 1) // K + 1)
    ans = min(ans, (H - x_max - 1 + K - 1) // K + 1)
    ans = min(ans, (y_min + K - 1) // K + 1)
    ans = min(ans, (W - y_max - 1 + K - 1) // K + 1)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# まずK回移動する
# 後は直前に開いた扉を進んでいけるので，辺への最短路を進む

H,W,K = LI()
A = [list(input()) for _ in range(H)]

s = (-1,-1)
for i in range(H):
    for j in range(W):
        if A[i][j] == 'S':
            s = (i,j)

def grid_bfs(S,s,default=-1):
    dist = [[default]*W for _ in range(H)]
    can_visit_mark = ['.','S']
    if S[s[0]][s[1]] not in can_visit_mark:
        return dist
    d = [(0,1),(0,-1),(1,0),(-1,0)]
    dist[s[0]][s[1]] = 0
    q = [s]
    counter = 1
    while q:
        q1 = []
        for now in q:
            for delta in d:
                new = (now[0]+delta[0], now[1]+delta[1])
                if 0 <= new[0] <= H-1 and 0 <= new[1] <= W-1:
                    if S[new[0]][new[1]] in can_visit_mark:  
                        if dist[new[0]][new[1]] == -1:
                            dist[new[0]][new[1]] = counter
                            q1.append(new)
        q = q1
        counter += 1
        if counter == K+1:
            break
    return dist

dist = grid_bfs(A,s)

min_ = float('inf')
for i in range(H):
    for j in range(W):
        if dist[i][j] != -1:
            temp = min(i,H-i-1,j,W-j-1)
            if temp < min_:
                min_ = temp

print(1+math.ceil(min_/K))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
flg = 0
for a in range(h):
    for b in range(w):
        if A[a][b] == 'S':
            sy, sx = a, b
            A[sy][sx] = 0
            flg = 1
            break
    if flg:
        break

q = deque([(sy, sx)])
L = []
min_dist = min(sy, h - sy - 1, sx, w - sx - 1)
while q:
    y, x = q.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + i, y + j
        if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == '.':
            A[ny][nx] = A[y][x] + 1
            min_dist = min(min_dist, min(ny, h - 1 - ny, nx, w - 1 - nx))
            if A[ny][nx] < k:
                q += [(ny, nx)]


print(1 - (- min_dist // k))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
q = deque()
for a in range(h):
    if 'S' in A[a]:
        sy = a; sx = A[a].index('S')
        q += [(sy, sx)]

A[sy][sx] = 0
min_dist = INF
while q:
    y, x = q.popleft()
    min_dist = min(min_dist, x, y, h - 1 - y, w - 1 - x)
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + i, y + j
        if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == '.':
            A[ny][nx] = A[y][x] + 1
            if A[ny][nx] > k:
                continue
            q += [(ny, nx)]

print(1-(-min_dist // k))

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w,k = map(int, input().split())
board = [list(input()) for i in range(h)]

for i in range(h):
    for j in range(w):
        if board[i][j] == "S":
            sx, sy = i, j

from collections import deque
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
def bfs(sx, sy):
    q = deque()
    q.append((sx, sy))
    used = [[0]*w for i in range(h)]
    ans = float("inf")
    while q:
        x,y = q.pop()
        if used[x][y]:
            continue
        used[x][y] = 1
        tmp = -(-min(x, h-1-x, y, w-1-y)//k)
        ans = min(ans, tmp+1)
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if abs(nx-sx)+abs(ny-sy)>k:
                continue
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == ".":
                if nx == 0 or nx == h-1 or ny == 0 or ny == w-1:
                    return 1
                if not used[nx][ny]:
                    q.append((nx,ny))
    return ans

ans = bfs(sx, sy)
print(ans)

Submission status: Accepted

Solution code:
import collections

def solve():
  def calc(x,y):
    cnt1=(x+k-1)//k
    cnt2=(w-1-x+k-1)//k
    cnt3=(y+k-1)//k
    cnt4=(h-1-y+k-1)//k
    return min(cnt1,cnt2,cnt3,cnt4)

  h,w,k=map(int,input().split())
  boards=[tuple(input()) for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if boards[i][j]=='S':
        sx=j
        sy=i
        break
  q=collections.deque()
  checked=[[0]*w for _ in range(h)]
  checked[sy][sx]=1
  q.append((sx,sy,0))
  ans=1+calc(sx,sy)
  while 1:
    if len(q)==0:
      break
    tx,ty,cnt=q.popleft()
    if cnt==k+1:
      break
    ans=min(ans,1+calc(tx,ty))
    if tx!=0 and boards[ty][tx-1]!='#' and checked[ty][tx-1]==0:
      checked[ty][tx-1]=1
      q.append((tx-1,ty,cnt+1))
    if tx!=w-1 and boards[ty][tx+1]!='#' and checked[ty][tx+1]==0:
      checked[ty][tx+1]=1
      q.append((tx+1,ty,cnt+1))
    if ty!=0 and boards[ty-1][tx]!='#' and checked[ty-1][tx]==0:
      checked[ty-1][tx]=1
      q.append((tx,ty-1,cnt+1))
    if ty!=h-1 and boards[ty+1][tx]!='#' and checked[ty+1][tx]==0:
      checked[ty+1][tx]=1
      q.append((tx,ty+1,cnt+1))
  print(ans)
solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
a = []
s = 0
for _ in range(H): a += list(input())[: -1]
for i in range(H * W):
  if a[i] == "S":
    s = i
    break
Q = dq([s])
d = [-1, 0, 1, 0]
dp = [float("inf")] * (H * W)
dp[s] = 0
while len(Q):
  p = Q.popleft()
  for k in range(4):
    q = p + d[k] + d[-1 - k] * W
    if q in range(H * W):
      if a[q] == "#": continue
      if dp[p] + 1 < dp[q]:
        dp[q] = dp[p] + 1
        Q.append(q)
res = float("inf")
for i in range(H * W):
  if dp[i] > K: continue
  n = i // W
  s = H - (i // W) - 1
  e = W - (i % W) - 1
  w = i % W
  res = min(res, -(-min(n, s, e, w) // K))
print(res + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import deque
INF = float("inf")

DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]


def solve(H: int, W: int, K: int, A: "List[str]"):

    y, x = -1, -1
    for i in range(1, H-1):
        for j in range(1, W-1):
            if A[i][j] == "S":
                y, x = i, j
                break
        if y != -1:
            break

    outer = INF
    outplace = (-1, -1)
    reachable = [[INF]*W for _ in range(H)]
    q = deque([(y, x, 0)])
    while len(q) > 0:
        y, x, d = q.popleft()

        # 到達可能な箇所で外に最も近い場所を探す
        dist = min([y, H-1-y, x, W-1-x])
        if dist < outer:
            outer = dist
            outplace = (y, x)

        if d == K:
            continue
        for dy, dx in zip(DY, DX):
            if not (0 <= y+dy < H):
                continue
            elif not (0 <= x+dx < W):
                continue
            elif A[y+dy][x+dx] == "#":
                continue
            else:
                if d+1 < reachable[y+dy][x+dx]:
                    reachable[y+dy][x+dx] = d+1
                    q.append((y+dy, x+dx, d+1))

    ans = 1 - (-outer // K)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, K, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
a=[list(input())for i in range(h)]
b=[[1]*w for i in range(h)]
c=0
for i in range(h):
    if c:
        break
    for j in range(w):
        if a[i][j]=="S":
            c=1
            p=[i,j]
            b[i][j]=0
def f(x,y):
    return min(x,w-y-1,y,h-x-1)
an=f(p[0],p[1])
q=[p]
c=0
while q and c!=k:
    c+=1
    d=[]
    x=[0,0,1,-1]
    y=[1,-1,0,0]
    for i,j in q:
        for s,t in zip(x,y):
            if 0<i+s<h-1 and 0<j+t<w-1:
                if b[i+s][j+t]:
                    if a[i+s][j+t]==".":
                        an=min(an,f(i+s,j+t))
                        b[i+s][j+t]=0
                        d.append([i+s,j+t])
            else:
                if a[i+s][j+t]==".":
                     print(1)
                     exit()
    q=d[::]
print(2+(an-1)//k)

Submission status: Accepted

Solution code:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

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

b = "#"
r = "."

for i in range(H):
  for j in range(W):
    if A[i][j] == b:
      A[i][j] = -1
    elif A[i][j] == r:
      A[i][j] = 0
    else:
      A[i][j] = 0
      S = [i, j]

if S[0] == 0 or S[0] == H - 1:
  print(0)
  exit()
if S[1] == 0 or S[1] == W - 1:
  print(0)
  exit()
g = gridMan(A)
g.makeWall()

L, r = g.dist(S)

ans = 10 ** 10
for i in range(H):
  for j in range(W):
    if 0 <= L[i][j] and L[i][j] <= K:
      t = min(i, j, H - i - 1, W - j - 1)
      if t == 0:
        print(1)
        exit()
      t = (t + K - 1) // K
      ans = min(ans, t)

print(ans + 1)