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:
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):
#    debug_print(maze)
    distance = [[inf]*w for _ in range(h)]
    def bfs():
        queue = deque()
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.popleft()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#'):
                    if distance[ny][nx]<=distance[y][x]+1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)
#    for v in D:
#        print(v)
    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):
#    debug_print(maze)
    distance = [[inf for _ in range(w)] for _ in range(h)]
    def bfs():
        queue = []
        queue.insert(0, s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#' and distance[ny][nx] == inf):
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)
#    print(D)
    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
def main():
    h, w, k = map(int, input().split())
    grid = ["."*(w+2)]+["."+input()+"." for _ in [0]*h]+["."*(w+2)]
    visit = [[False]*(w+2) for _ in [0]*(h+2)]
    for i in range(h+2):
        for j in range(w+2):
            if grid[i][j] == "S":
                start = (i, j)
                break
    visit[start[0]][start[1]] = True
    q = [start]
    for i in range(k):
        q2 = []
        while q:
            x, y = q.pop()
            if x-1 >= 0:
                if grid[x-1][y] == "." and visit[x-1][y] is False:
                    q2.append((x-1, y))
                    visit[x-1][y] = True
            if x+1 <= h+1:
                if grid[x+1][y] == "." and visit[x+1][y] is False:
                    q2.append((x+1, y))
                    visit[x+1][y] = True
            if y-1 >= 0:
                if grid[x][y-1] == "." and visit[x][y-1] is False:
                    q2.append((x, y-1))
                    visit[x][y-1] = True
            if y+1 <= w+1:
                if grid[x][y+1] == "." and visit[x][y+1] is False:
                    q2.append((x, y+1))
                    visit[x][y+1] = True
        q = q2
    dist = 10**9
    for i in range(h+2):
        for j in range(w+2):
            if visit[i][j]:
                dist = min([dist, i, h+1-i, j, w+1-j])
    print((max(dist-1, 0)-1)//k+2)


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
from collections import deque
def resolve():
    h,w,k=map(int,input().split())
    G=[list(input()) for _ in range(h)]
    D=[(1,0),(-1,0),(0,1),(0,-1)]
    for i,j in product(range(h),range(w)):
        if(G[i][j]=='S'):
            i0,j0=i,j
            break

    dist=[[INF]*w for _ in range(h)]
    dist[i0][j0]=0
    # BFS
    Q=deque([(i0,j0)])
    while(Q):
        i,j=Q.popleft()
        for di,dj in D:
            ni=i+di; nj=j+dj
            if(not (0<=ni<h and 0<=nj<w)): continue
            if(dist[ni][nj]!=INF or G[ni][nj]=='#'): continue
            dist[ni][nj]=dist[i][j]+1
            Q.append((ni,nj))

    # 後は距離が k 以下の点から一直線に外に向かえばよい
    ans=INF
    for i,j in product(range(h),range(w)):
        if(dist[i][j]<=k):
            d=min(i,j,h-i-1,w-j-1)
            if(d==0):
                print(1)
                return
            else:
                ans=min(ans,2+(d-1)//k)
    print(ans)
resolve()

Submission status: Accepted

Solution code:
from collections import deque


h, w, k = map(int, input().split())
a = [input() for i in range(h)]
INF= 10**9

for i in range(h):
    for j in range(w):
        if a[i][j] == "S":
            si, sj = i, j
            break

cnt = [[INF] * w for i in range(h)]
cnt[si][sj] = 0
q = deque([(si, sj, 0)])
while q:
    pi, pj, cost = q.popleft()
    for nxi, nxj in [(pi+1, pj), (pi, pj+1), (pi-1, pj), (pi, pj-1)]:
        if not (0 <= nxi < h and 0 <= nxj < w):
            continue
        if a[nxi][nxj] == "." and cost + 1 < cnt[nxi][nxj] and cost + 1 <= k:
            cnt[nxi][nxj] = cost + 1
            q.append((nxi, nxj, cost + 1))

ans = 10**9
for i in range(h):
    for j in range(w):
        if cnt[i][j] <= k:
            ans = min(ans, -((-i)//k), -((-(h-i-1))//k), -((-j)//k), -((-(w-j-1))//k))

print(ans+1)

Submission status: Accepted

Solution code:
from collections import deque

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

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

A = []

for i in range(H):

    a = list(input())
    A.append(a)

q = deque([])

#print (A)

for i in range(H):

    for j in range(W):

        if A[i][j] == "S":
            q.append([i,j])
            A[i][j] = 0

while len(q) > 0:

    now = q.popleft()
    ni = now[0]
    nj = now[1]

    if A[ni][nj] < K:
        if ni-1 >= 0 and A[ni-1][nj] != "#":
            if A[ni-1][nj] == "." or A[ni][nj]+1 < A[ni-1][nj]:
                A[ni-1][nj] = A[ni][nj] + 1
                q.append([ni-1,nj])

        if ni+1 < H and A[ni+1][nj] != "#":
            if A[ni+1][nj] == "." or A[ni][nj]+1 < A[ni+1][nj]:
                A[ni+1][nj] = A[ni][nj] + 1
                q.append([ni+1,nj])

        if nj-1 >= 0 and A[ni][nj-1] != "#":
            if A[ni][nj-1] == "." or A[ni][nj]+1 < A[ni][nj-1]:
                A[ni][nj-1] = A[ni][nj] + 1
                q.append([ni,nj-1])

        if nj+1 < W and A[ni][nj+1] != "#":
            if A[ni][nj+1] == "." or A[ni][nj]+1 < A[ni][nj+1]:
                A[ni][nj+1] = A[ni][nj] + 1
                q.append([ni,nj+1])

ans = float("inf")
#print (A)

for i in range(H):

    for j in range(W):

        if A[i][j] not in [".","#"]:
            ans = min(ans , 1 + updiv(i,K) , 1 + updiv(j,K) , 1 + updiv(H-i-1,K), 1 + updiv(W-j-1, K))

print (ans)

Submission status: Accepted

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


def main():
    H, W, K = map(int, input().split())
    state = [list(input()) for _ in range(H)]


    q = []
    checked = [[False]*W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if state[h][w] == "S":
                q.append((h, w))
                checked[h][w] = True

    goal = False
    for _ in range(K):
        qq = []
        for h, w in q:
            if h == 0 or h == H-1 or w == 0 or w == W-1:
                goal = True
                break
            nexts = [(h, w-1), (h, w+1), (h-1, w), (h+1, w)]
            for nh, nw in nexts:
                if state[nh][nw] == "." and not checked[nh][nw]:
                    checked[nh][nw] = True
                    qq.append((nh, nw))
        q = qq
    if goal:
        print(1)
    else:
        ans = 10**14
        for h in range(H):
            for w in range(W):
                if checked[h][w]:
                    d1 = min(h, H-1-h)
                    d2 = min(w, W-1-w)
                    D = min(d1//K + min(d1%K, 1), d2//K + min(d2%K, 1))
                    ans = min(D+1, ans)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    Dy = [1,0,-1,0]
    Dx = [0,-1,0,1]
    
    H, W, K = map(int, input().split())
    A = [input() for _ in range(H)]
    Closed = [[False]*W for _ in range(H)]
    for y, a in enumerate(A):
        for x, aa in enumerate(a):
            if aa=="S":
                ys, xs = y, x
    q = [(ys, xs)]
    Closed[ys][xs] = True
    reachable = [(ys, xs)]
    for _ in range(K):
        q_new = []
        for y_old, x_old in q:
            for dy, dx in zip(Dy, Dx):
                y, x = y_old + dy, x_old + dx
                if not (0<=y<H and 0<=x<W):
                    continue
                if not Closed[y][x] and A[y][x]==".":
                    Closed[y][x] = True
                    reachable.append((y, x))
                    q_new.append((y, x))
        q = q_new
    mi = float("inf")
    for y, x in reachable:
        mi = min(mi, x, y, W-1-x, H-1-y)
    print((mi-1)//K+2)

main()

Submission status: Accepted

Solution code:
h, w, k = [ int(v) for v in input().split() ]
field = [ list(input()) for i in range(h) ]
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
for i in range(h):
    for j in range(w):
        if field[i][j] == "S":
            s = (i,j)

def nearest(y, x):
    return min(y,h-1-y,x,w-1-x) 


def bfs():
    global field, adjust_list, s
    search_list = [s]
    for _ in range(k):
        new_search_list = []
        for i in search_list:
            for j in adjust_list:
                if 0 <= i[0]+j[0] < h and 0 <= i[1]+j[1] < w:
                    if field[i[0]+j[0]][i[1]+j[1]] == ".":
                        field[i[0]+j[0]][i[1]+j[1]] = "S"
                        new_search_list.append((i[0]+j[0],i[1]+j[1]))
        search_list = new_search_list
    return

bfs()
print(1 + ( min([ nearest(i,j) for j in range(w) for i in range(h) if field[i][j] == "S" ]) + k - 1 ) // k)

Submission status: Accepted

Solution code:
from collections import deque

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

sx, sy = 0, 0
for y in range(H) :
    flag = False
    for x in range(W) :
        if A[y][x] == 'S' :
            sx, sy = x, y
            flag = True
            break
    
    if flag :
        break


dist = [[-1] * W for _ in range(H)]
dist[sy][sx] = 0
q = deque([(sy, sx)])
while q :
    y, x = q.popleft()
    if dist[y][x] == K :
        continue
    
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)) :
        nx, ny = x + dx, y + dy
        if 0 <= nx < W and 0 <= ny < H and dist[ny][nx] == -1 and A[ny][nx] == '.' :
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))

ret = float('inf')
for y in range(H) :
    for x in range(W) :
        if dist[y][x] < 0 :
            continue
        
        ret = min(ret, 1 + (min(H - y, y + 1, W - x, x + 1) - 1 + K - 1) // K)
        
print(ret)

Submission status: Accepted

Solution code:
from collections import*
H,*A=open(0)
H,W,K=map(int,H.split())
*A,=map(list,A)
for i,a in enumerate(A):
	if'S'in a:j=a.index('S');Q=deque([(0,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,~i+H,~j+W)
	if c<K:
		for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
			if H>h>-1<w<W and'.'==A[h][w]:A[h][w]=0;Q+=(c+1,h,w),
print(1--d//K)

Submission status: Accepted

Solution code:
from collections import*
H,*A=open(0)
H,W,K=map(int,H.split())
*A,=map(list,A)
for i,a in enumerate(A):
	if'S'in a:j=a.index('S');Q=deque([(0,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c<K:
		for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
			if H>h>-1<w<W and'.'==A[h][w]:A[h][w]=0;Q+=(c+1,h,w),
print(1--d//K)

Submission status: Accepted

Solution code:
import collections as C
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=C.deque([(0,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c<K:
		for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
			if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=(c+1,h,w),
print(1--d//K)

Submission status: Accepted

Solution code:
import collections as C
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=C.deque([(1,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=(c+1,h,w),
print(1--d//K)

Submission status: Accepted

Solution code:
import collections as C
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=C.deque([(1,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=deque([(1,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1--d//K)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i in range(H):
	if"S"in A[i]:y,x=i,A[i].index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>=K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]=""
			Q+=[(c+1,ni,nj)]
print(1-(-d//K))

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]="#"
			Q+=[(c+1,ni,nj)]
print(-(-d//K)+1)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i, a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if d<1:break
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]="#"
			Q+=[(c+1,ni,nj)]
print(-(-d//K)+1)

Submission status: Accepted

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
y,x=(0,0)
for i, a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if d<1:break
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]="#"
			Q.append((c+1,ni,nj))
print(-(-d//K)+1)

Submission status: Accepted

Solution code:
from collections import deque

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
	if "S" in a:
		Si, Sj = (i, a.index("S"))
		break

dist = float("inf")

Q = deque([(0, Si, Sj)])
while Q:
	cnt, i, j = Q.popleft()

	dist = min(dist, i, j, H - i - 1, W - j - 1)
	if dist == 0:
		break

	if cnt >= K:
		continue

	for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
		if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
			A[ni][nj] = "#"
			Q.append((cnt + 1, ni, nj))

print(-(-dist // K) + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        A[Si][Sj] = "#"
        break

dist = float("inf")

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    dist = min(dist, i, j, H - i - 1, W - j - 1)
    if dist == 0:
        break

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((cnt + 1, ni, nj))

print(-(-dist // K) + 1)

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        A[Si][Sj] = "c"
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    distance = min(distance, i, j, H - i - 1, W - j - 1)
    if distance == 0:
        break

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "c"
            Q.append((cnt + 1, ni, nj))

print(-(-distance // K) + 1)

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        A[Si][Sj] = "c"
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "c"
            Q.append((cnt + 1, ni, nj))

print(-(-distance // K) + 1)

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((cnt + 1, ni, nj))

print(-(-distance // K) + 1)

Submission status: Accepted

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    dist, i, j = Q.popleft()
    if dist > K:
        break

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    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] == ".":
            A[ni][nj] = "#"
            Q.append((dist + 1, ni, nj))

print(-(-distance // K) + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

chart = [list(input()) for _ in range(H)]

start = (-1, -1)
for h in range(H):
    for w in range(W):
        if chart[h][w] == 'S':
            start = (h, w)
            chart[h][w] = '.'

minDist  = [[float('inf')] * W for _ in range(H)]
que = deque([(start[0], start[1], 0)])
while que:
    nh, nw, dist = que.popleft()

    if minDist[nh][nw] <= dist:
        continue

    minDist[nh][nw] = dist
    if dist == K:
        continue

    for toH in [nh - 1, nh + 1]:
        if toH < 0 or toH >= H:
            continue
        if chart[toH][nw] == '.':
            que.append((toH, nw, dist + 1))
    for toW in [nw - 1, nw + 1]:
        if toW < 0 or toW >= W:
            continue
        if chart[nh][toW] == '.':
            que.append((nh, toW, dist + 1))

ans = float('inf')
for h in range(H):
    for w in range(W):
        if minDist[h][w] == float('inf'):
            continue
        d = min(h, w, H - h - 1, W - w - 1)
        if d == 0:
            ans = min(ans, 1)
        else:
            ans = min(ans, -(-d // K) + 1)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

maze = [[x for x in input()] for _ in range(h)]

sx = 0
sy = 0

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

d = [[float('inf')]*w for _ in range(h)]
d[sy][sx] = 0

q = deque([[sy,sx]])
c = 0

visited = [[False]*w for _ in range(h)]
visited[sy][sx] = True

while q:
    y,x = q.popleft()
    for j,k in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny,nx = y+j,x+k
        if maze[ny][nx] == '.' and not visited[ny][nx]:
            d[ny][nx] = d[y][x] + 1
            if ny in {0,h-1} or nx in {0,w-1}:
                if d[ny][nx] <= K:
                    print(1)
                    exit()
                else:
                    continue
            else:
                visited[ny][nx] = True
                if d[ny][nx] == K:
                    continue
                else:
                    q.append([ny,nx])
    

def BFS(sy,sx):
    visited = [[-1]*w for _ in range(h)]
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    while q:
        y,x = q.popleft()
        if y == 0 or y == h-1 or x == 0 or x == w-1:
            return visited[y][x]
        for l,k in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_y,new_x = y+l,x+k
            if visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                q.append([new_y,new_x])

ans = float('inf')

for i in range(h):
    for j in range(w):
        if d[i][j] <= K:
            ans = min(ans,min(i,h-1-i,j,w-1-j))

print((ans-1) // K +2)