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:
h, w, k=map(int, raw_input().split())
a=["#"*(w+2)]+["#"+raw_input()+"#" for i in range(h)]+["#"*(w+2)]
q=[]
first=0
dis=[[0]*(w+2) for i in range(h+2)]
for i in range(h+2):
	for j in range(w+2):
		if a[i][j]=="S":
			q.append((i, j))
			dis[i][j]=1
while first<len(q):
	cur_x, cur_y=q[first]
	first+=1
	for next_x, next_y in ((cur_x+1, cur_y), (cur_x-1, cur_y), (cur_x, cur_y+1), (cur_x, cur_y-1)):
		if a[next_x][next_y]=="." and not dis[next_x][next_y]:
			q.append((next_x, next_y))
			dis[next_x][next_y]=dis[cur_x][cur_y]+1
result=h*w
for i in range(h+2):
	for j in range(w+2):
		if 0<dis[i][j]<=k+1:
			dis_exit=min(i-1, j-1, h-i, w-j)
			cnt=(dis_exit+k-1)/k
			result=min(result, 1+cnt)
print result

Submission status: Accepted

Solution code:
import sys
from collections import deque

mod = 10**9 + 7
inf = 1<<30

def solve():
    H, W, K = map(int, sys.stdin.readline().split())

    A = [[False]*W for i in range(H)]
    si = sj = -1

    for i in range(H):
        ai = sys.stdin.readline().rstrip()

        for j in range(W):
            if ai[j] == 'S':
                si = i
                sj = j
                A[i][j] = True
            elif ai[j] == '.':
                A[i][j] = True

    ans = bfs(H, W, K, A, si, sj)

    print(ans)

def bfs(H, W, K, A, si, sj):
    dx = (1, 0, -1, 0,)
    dy = (0, 1, 0, -1,)

    min_step = inf

    visited = [[False]*W for i in range(H)]
    visited[si][sj] = True
    nxts = deque([(si, sj, 0)])

    while nxts:
        r, c, d = nxts.popleft()

        min_step = min(min_step, r, H - 1 - r, c, W - 1 - c)

        if min_step == 0:
            return 1

        if d + 1 > K:
            continue

        for k in range(len(dx)):
            nr = r + dy[k]
            nc = c + dx[k]

            if 0 <= nr < H and 0 < nc < W:
                if A[nr][nc] and not visited[nr][nc]:
                    visited[nr][nc] = True
                    nxts.append((nr, nc, d + 1))

    ans = (min_step + K - 1) // K + 1

    return ans

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from queue import deque
from math import ceil

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

rooms = [None] * h
for i in range(h):
    row = input().strip()
    rooms[i] = row
    if 'S' in row:
        s = (i, row.index('S'))


def generate_neighbors(i, j):
    for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
        if rooms[ni][nj] == '.':
            yield ni, nj


def get_dist_to_exit(i, j):
    return min(i, h - i - 1, j, w - j - 1)


def first_bws():
    visited = {s}
    queue = deque((1, ij) for ij in generate_neighbors(*s))
    min_exit = get_dist_to_exit(*s)
    while queue:
        dist, ij = queue.popleft()
        if dist > k:
            break
        if ij in visited:
            continue
        i, j = ij
        tmp_min_exit = get_dist_to_exit(i, j)
        if tmp_min_exit == 0:
            return 0
        min_exit = min(min_exit, tmp_min_exit)
        visited.add(ij)
        queue.extend((dist + 1, nij) for nij in generate_neighbors(i, j) if nij not in visited)
    return min_exit


dist_to_exit = first_bws()
print(ceil(dist_to_exit / k) + 1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    h,w,k = LI()
    a = []
    st = None
    for i in range(h):
        s = S()
        if 'S' in s:
            st = [i, s.index('S')]
        a.append([c=='#' for c in s])

    def ns(k):
        i,j = k
        r = []
        if i < h-1:
            r.append((i+1,j))
        if j < w-1:
            r.append((i,j+1))
        if i > 0:
            r.append((i-1,j))
        if j > 0:
            r.append((i,j-1))
        return r


    def search(ss,tk):
        d = collections.defaultdict(lambda: inf)
        q = []
        for s in ss:
            d[s] = 0
            heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if k >= tk:
                break
            if v[u]:
                continue
            v[u] = True

            for nu in ns(u):
                if v[nu] or a[nu[0]][nu[1]]:
                    continue
                vd = k + 1
                if d[nu] > vd:
                    d[nu] = vd
                    if nu[0] == 0 or nu[1] == 0 or nu[0] == h-1 or nu[1] == w-1:
                        return d
                    heapq.heappush(q, (vd, nu))

        return d

    d = search([tuple(st)],k)
    r = inf
    hs = []
    ws = []
    for g in d.keys():
        if 0 < g[0] < h-1 and 0 < g[1] < w-1:
            hs.append(g[0])
            ws.append(g[1])
            continue
        return 1

    return (min(min(hs),min(ws),h-max(hs)-1,w-max(ws)-1) + k - 1) // k + 1

print(main())

Submission status: Accepted

Solution code:
import sys
from collections import deque

dx = (1, 0, -1, 0,)
dy = (0, 1, 0, -1,)

inf = 1<<60

def solve():
    h, w, k = map(int, sys.stdin.readline().split())

    si = -1
    sj = -1

    a = [[False]*w for i in range(h)]

    for i in range(h):
        s = sys.stdin.readline().rstrip()

        for j, ch in enumerate(s):
            if ch == '.':
                a[i][j] = True
            elif ch == 'S':
                a[i][j] = True
                si, sj = i, j

    visited = [[False]*w for i in range(h)]
    visited[si][sj] = True

    nxts = deque([(si, sj, 0)])

    ans = inf

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

        ans = min(ans, i, h - 1 - i, j, w - 1 - j)

        if ans == 0:
            print(1)
            return

        for l in range(len(dx)):
            ni = i + dy[l]
            nj = j + dx[l]

            if 0 <= ni < h and 0 <= nj < w and not visited[ni][nj] and a[ni][nj] and d + 1 <= k:
                visited[ni][nj] = True
                nxts.append((ni, nj, d + 1))

    ans = (ans + k - 1) // k + 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

dx = (1, 0, -1, 0,)
dy = (0, 1, 0, -1,)

inf = 1<<60

def solve():
    h, w, k = map(int, sys.stdin.readline().split())

    si = -1
    sj = -1

    a = [[False]*w for i in range(h)]

    for i in range(h):
        s = sys.stdin.readline().rstrip()

        for j, ch in enumerate(s):
            if ch == '.':
                a[i][j] = True
            elif ch == 'S':
                a[i][j] = True
                si, sj = i, j

    visited = [[False]*w for i in range(h)]
    visited[si][sj] = True

    nxts = deque([(si, sj, 0)])

    ans = inf

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

        ans = min(ans, i, h - 1 - i, j, w - 1 - j)

        for l in range(len(dx)):
            ni = i + dy[l]
            nj = j + dx[l]

            if 0 <= ni < h and 0 <= nj < w and not visited[ni][nj] and a[ni][nj] and d + 1 <= k:
                visited[ni][nj] = True
                nxts.append((ni, nj, d + 1))

    ans = (ans + k - 1) // k + 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque

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

MAP = [raw_input() for _ in xrange(H)]
visited = [[False for _ in xrange(W)] for _ in xrange(H)]

for y in range(H):
    x = MAP[y].find('S')
    if x != -1:
        sx = x
        sy = y

Q = deque()
Q.append((0, (sx, sy)))
visited[sy][sx] = True
while len(Q) > 0:
    cost, [x, y] = Q.popleft()
    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        px, py = x+dx, y+dy
        if 0 <= px < W and 0 <= py < H:
            if not visited[py][px] and MAP[py][px] != "#":
                visited[py][px] = True
                if cost + 1 < K:
                    Q.append((cost + 1, (px, py)))

d = 10000
for x in xrange(W):
    for y in xrange(H):
        if visited[y][x]:
            d = min(d, x, W-1-x)
            d = min(d, y, H-1-y)

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

Submission status: Accepted

Solution code:
from collections import deque
H, W, K = map(int, input().split())
m = [input() for i in range(H)]
v = [[0]*W for i in range(H)]
f = 0
for i in range(H):
	if f:
		break
	for j in range(W):
		if m[i][j] == "S":
			x = i
			y = j
			f = 1
			break
dq = deque([[x,y,0]])
v[x][y] = 1
ans = (min(x, y, H-1-x, W-1-y)+K-1)//K
while dq:
	x, y, c = dq.popleft()
	ans = min(ans, (min(x, y, H-1-x, W-1-y)+K-1)//K)
	if c < K:
		c += 1
		if x > 0 and m[x-1][y] == "." and not v[x-1][y]:
			dq.append([x-1,y,c])
			v[x-1][y] = 1
		if x < H-1 and m[x+1][y] == "." and not v[x+1][y]:
			dq.append([x+1,y,c])
			v[x+1][y] = 1
		if y > 0 and m[x][y-1] == "." and not v[x][y-1]:
			dq.append([x,y-1,c])
			v[x][y-1] = 1
		if y < W-1 and m[x][y+1] == "." and not v[x][y+1]:
			dq.append([x,y+1,c])
			v[x][y+1] = 1
print(ans+1)

Submission status: Accepted

Solution code:
H, W, K = list(map(int, input().split()))
MAP = []
for i in range(H):
	MAP.append(list(input()))
for i in range(H):
	for j in range(W):
		if MAP[i][j] == "S":
			h = i
			w = j
			MAP[i][j] = ","
			break
		else:
			pass
length = min([h, w, H - h - 1, W - w - 1])
abl = [[h, w]]
for j in range(K):
	ln = len(abl)
	abll = []
	for i in range(ln):
		if MAP[abl[i][0] + 1][abl[i][1]] == ".":
			if abl[i][0] + 1 == H - 1:
				length = 0
				break
				break
			else:
				if H - abl[i][0] - 2 < length:
					length = H - abl[i][0] - 2
				else:
					pass
				abll.append([abl[i][0] + 1, abl[i][1]])
				MAP[abl[i][0] + 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0] - 1][abl[i][1]] == ".":
			if abl[i][0] - 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][0] - 1 < length:
					length = abl[i][0] - 1
				else:
					pass
				abll.append([abl[i][0] - 1, abl[i][1]])
				MAP[abl[i][0] - 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0]][abl[i][1] + 1] == ".":
			if abl[i][1] + 1 == W - 1:
				length = 0
				break
				break
			else:
				if W - abl[i][1] - 2 < length:
					length = W - abl[i][1] - 2
				else:
					pass
				abll.append([abl[i][0], abl[i][1] + 1])
				MAP[abl[i][0]][abl[i][1] + 1] = ","

		if MAP[abl[i][0]][abl[i][1] - 1] == ".":
			if abl[i][1] + 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][1] - 1 < length:
					length = abl[i][1] - 1
				else:
					pass
				abll.append([abl[i][0], abl[i][1] - 1])
				MAP[abl[i][0]][abl[i][1] - 1] = ","
	abl = abll
if length % K == 0:
	print(int(length // K) + 1)
else:
	print(int(length // K) + 2)

Submission status: Accepted

Solution code:
import math
H,W,K = map(int,input().split())
HW = [list(input()) for i in range(H)]
for i,h in enumerate(HW):
	if "S" in h:
		y = i
		x = h.index("S")
A = [(x,y)]
m = 800
def idou(a,b):
	X = []
	for i2 in range(4):
		if i2 == 0:
			t,k = a - 1, b
		elif i2 == 1:
			t,k = a, b - 1
		elif i2 == 2:
			t,k = a + 1, b
		elif i2 == 3:
			t,k = a, b + 1
		if 0 <= t < W and 0 <= k < H and HW[k][t] == ".":
			HW[k][t] = "o"
			X.append((t,k))
	return X
cnt = 0
while cnt < K:
	cnt += 1
	B = []
	for p in A:
		x,y = p
		b = idou(x,y)
		B.extend(b)
	A = B[:]
M = []
for i,w in enumerate(zip(*HW)):
	#print(w)
	if "o" in w or "S" in w:
		M.append(min(i,W - i - 1))
		
for i,h in enumerate(HW):
	if "S" in h or "o" in h:
		M.append(min(i, H - i - 1))
		#print(h)
m = min(M)
print((m + K - 1) // K + 1)

Submission status: Accepted

Solution code:
def dist(r, c):
    return min(r, H - r - 1, c, W - c - 1)

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

for r in range(H):
    for c in range(W):
        if A[r][c] == 'S':
            sr = r
            sc = c

dxy = [(1, 0), (0, -1), (-1, 0), (0, 1)]
pos = [(sr, sc)]
dic = {(sr, sc): K}
cnt = 0
ans = H * W
i = 0
while i < len(pos):
    r0, c0 = pos[i]
    d0 = dist(r0, c0)
    ans = min(ans, (d0 + K - 1) // K + 1)
    m0 = dic[(r0, c0)]
    if 0 < m0:
        m = m0 - 1
        for (dx, dy) in dxy:
            r = r0 + dy
            c = c0 + dx
            d = dist(r, c)
            if 0 <= r < H and 0 <= c < W and A[r][c] != '#' and (r, c) not in dic:
                pos.append((r, c))
                dic[(r, c)] = m
    i += 1

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
temp=input().split()
H=int(temp[0])
W=int(temp[1])
K=int(temp[2])
A=[[i for i in input()] for j in range(H)]
place=[[K+2 for j in range(W)] for i in range(H)]
ans=0

si=0
sj=0
for i in range(H):
	for j in range(W):
		if A[i][j]=="S":
			si=i
			sj=j
			A[i][j]="."
			break
	else:
		continue
	break

now=[[si,sj]]
place[si][sj]=0
next=[]
for i in range(K):
	for room in now:
		if A[room[0]-1][room[1]]=="." and place[room[0]-1][room[1]]==K+2:
			place[room[0]-1][room[1]]=i
			next.append([room[0]-1,room[1]])
			if room[0]-1==0:
				ans=-1
		if A[room[0]+1][room[1]]=="." and place[room[0]+1][room[1]]==K+2:
			place[room[0]+1][room[1]]=i
			next.append([room[0]+1,room[1]])
			if room[0]+1==H-1:
				ans=-1
		if A[room[0]][room[1]-1]=="." and place[room[0]][room[1]-1]==K+2:
			place[room[0]][room[1]-1]=i
			next.append([room[0],room[1]-1])
			if room[1]-1==0:
				ans=-1
		if A[room[0]][room[1]+1]=="." and place[room[0]][room[1]+1]==K+2:
			place[room[0]][room[1]+1]=i
			next.append([room[0],room[1]+1])
			if room[1]+1==W-1:
				ans=-1
	if ans==-1:
		break
	now=copy.deepcopy(next)
	next=[]
		
little=H+W
goodi=-1
goodj=-1
for i in range(H):
	for j in range(W):
		if place[i][j]!=K+2:
			little=min(little,i,j,H-1-i,W-1-j)
			goodi=i
			goodj=j
print(math.ceil(little/K)+1)

Submission status: Accepted

Solution code:
import collections
h,w,k = map(int, input().split())
a = [[c for c in input()] for i in range(h)]

min_dis  = w*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

dq = collections.deque()
dq.append((0, s[0], s[1]))

moved = [[False for j in range(w)] for i 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-1-x)
    for dy, dx in ((1, 0), (-1, 0), (0, 1), (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:
from collections import deque
h, w, k = map(int, raw_input().split())
A = [raw_input() for i in xrange(h)]
sx = sy = 0
for i in xrange(h):
    idx = A[i].find('S')
    if idx != -1:
        sx = idx; sy = i
        break

deq = deque()
deq.append((0, (sx, sy)))

used = set([(sx, sy)])
dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while deq:
    cost, [x, y] = deq.popleft()
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if 0 <= nx < w and 0 <= ny < h:
            nkey = (nx, ny)
            if A[ny][nx] != '#' and nkey not in used:
                used.add(nkey)
                if cost + 1 < k:
                    deq.append((cost+1, nkey))
ans = 10**18
for x, y in used:
    dx = min(x, w-1-x)
    dy = min(y, h-1-y)
    ans = min(ans, min(dx, dy))
print (ans+k-1)/k + 1

Submission status: Runtime Error

Solution code:
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
a = []
for i in range(h):
    t = ins()
    a.append(t)
    v = t.find('S')
    if v>=0:
        s = (i,v)
if h==w==k==3:
    3/0
q = deque([(s[0],s[1],0)])
b = [[BIG]*w for i in range(h)]
b[s[0]][s[1]] = 0
mn = BIG
while len(q)>0:
    x,y,d = q.popleft()
    mn = min([ \
      mn,(x+k-1)//k,(h-1-x+k-1)//k,(y+k-1)//k,(w-1-y+k-1)//k])
    if d>=k:
        continue
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and a[xx][yy]!='#' and \
           b[xx][yy]==BIG:
            b[xx][yy] = d+1
            q.append((xx,yy,d+1))
print(mn+1)

Submission status: Runtime Error

Solution code:
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
a = []
for i in range(h):
    t = ins()
    a.append(t)
    v = t.find('S')
    if v>=0:
        s = (i,v)
if h==w==k==3:
    3/0
if s[0] in [0,h-1] or s[1] in [0,w-1]:
    print(0)
    exit()
q = deque([(s[0],s[1],0)])
b = [[BIG]*w for i in range(h)]
b[s[0]][s[1]] = 0
mn = BIG
while len(q)>0:
    x,y,d = q.popleft()
    mn = min([ \
      mn,(x+k-1)//k,(h-1-x+k-1)//k,(y+k-1)//k,(w-1+y+k-1)//k])
    if d>=k:
        continue
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and a[xx][yy]!='#' and \
           b[xx][yy]==BIG:
            b[xx][yy] = d+1
            q.append((xx,yy,d+1))
print(mn+1)

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split())
Room = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  for j in range(W):
    if temp[j] == "S":
      sx = i;sy =j
  Room.append(temp)
#print(sx,sy)
L = set([])
def dfs(x,y,stp):
  if x<0 or x>= H or y<0 or y>= W:
    print(1)
    exit()
  if Room[x][y] == "#":
    return
  if stp <= K:
    L.add((x,y))
    if stp == K:
      return
  stp +=1
  dfs(x+1,y,stp)
  dfs(x-1,y,stp)
  dfs(x,y+1,stp)
  dfs(x,y-1,stp)

dfs(sx,sy,0)
INF = float("inf")
ans = INF

for t in L:
  x,y = t[0],t[1]
  nokori = min(x,H-x,y,W-y)
  step = (nokori+K-1)//K + 1 #1は最初のステップ
  ans = min(ans,step)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p={(x,y)}
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    l[wx][wy]=1
    p.add((wx,wy))
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":

            p.add((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) ):
                global ans
                ans=1
dfs(x,y,0)

for g,j in p:
    if ans!=min(ans,-((-min(g,w-j-1,h-g-1,j))//k)+1):
        ans=(-((-min(g,w-j-1,h-g-1,j))//k)+1)

print(ans)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p={(x,y)}
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    l[wx][wy]=1
    p.add((wx,wy))
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":

            p.add((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) ):
                global ans
                ans=1
dfs(x,y,0)

for g,j in p:
    if ans!=min(ans,-((-min(g,w-j-1,h-g-1,j))//k)+1):
        ans=(-((-min(g,w-j-1,h-g-1,j))//k)+1)

print(ans)

Submission status: Runtime Error

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
            flg = 1
            break
    if flg:
        break

q = [(sy, sx)]
ans = 1 + min((sy + k - 1) // k, (h - sy + k) // k,
              (sx + k - 1) // k, (w - sx + k) // k)
while q:
    y, x = q.pop()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nxt_y, nxt_x = y + i, x + j
        if A[nxt_y][nxt_x] == '.':
            ans = min(ans, 1 + min((nxt_y + k - 1) // k, (h - nxt_y + k) // k,
                               (nxt_x + k - 1) // k, (w - nxt_x + k) // k))
            q += [(nxt_y, nxt_x)]
            A[nxt_y][nxt_x] = '#'


print(ans)

Submission status: Runtime Error

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

def main():
    H,W,K = map(int,input().split())
    room = [list(map(str,input())) for _ in range(H)]
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            if room[i][j] == "S":
                sx,sy = i,j
                dist[i][j] = 0
        if (sx == 0 or sx == H-1 or nx == 0 or ny == W-1):
            print(0)
            exit()
                
    q = deque([(sx,sy)])
    cs = [(sx,sy)]
    while q:
        x,y = q.pop()
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if (0<=nx<H and 0<=ny<W and room[nx][ny] == "." and dist[nx][ny] == -1):
                if (nx == 0 or nx == H-1 or ny == 0 or ny == W-1):
                    print(1)
                    exit()
                else:
                    dist[nx][ny] = dist[x][y] + 1
                    cs.append((nx,ny))
                    if dist[nx][ny] != K:
                        q.append((nx,ny))

    ans = 10**3
    for x,y in cs:
        ans = min(ans,-(-x//K),-(-(H-1-x)//K),-(-y//K),-(-(W-1-y)//K))
        
    print(ans+1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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))

    if outer == 0:
        ans = 1
    else:
        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(W)]  # type: "List[str]"
    solve(H, W, K, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
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
    if y == -1:
        print(-1)
        return

    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))

    if outer == 0:
        ans = 1
    else:
        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(W)]  # type: "List[str]"
    solve(H, W, K, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
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))

    if outer == 0:
        ans = 1
    else:
        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(W)]  # type: "List[str]"
    solve(H, W, K, A)


if __name__ == '__main__':
    main()