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: Runtime Error

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 = []
        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)
#    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: Runtime Error

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

    print(dist)

    後は距離が 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: Runtime Error

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)*'.'==A[h][w]:A[h][w]=0;Q+=(c+1,h,w),
print(1--d//K)

Submission status: Runtime Error

Solution code:
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i in range(W):
	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: Runtime Error

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

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

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

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H or 0 <= nj < W) and A[ni][nj] == "#":
            continue

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Submission status: Runtime Error

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

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0

ans = INF

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

    ans = min(
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H or 0 <= nj < W) and A[ni][nj] == "#":
            continue

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Submission status: Runtime Error

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

dist = [[INF] * W for _ in range(W)]
dist[Si][Sj] = 0


ans = INF

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

    ans = min(
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H or 0 <= nj < W) and A[ni][nj] == "#":
            continue

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Submission status: Runtime Error

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

dist = [[INF] * W for _ in range(W)]
dist[Si][Sj] = 0


ans = INF

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

    ans = min(
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H or 0 <= nj < W) or A[ni][nj] == "#":
            continue

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Submission status: Runtime Error

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

dist = [[INF] * W for _ in range(W)]
dist[Si][Sj] = 0


ans = INF

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

    ans = min(
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W) or A[ni][nj] == "#":
            continue

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Submission status: Runtime Error

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

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] == '.':
            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:
                q.append([ny,nx])
                c += 1
    if c >= 4*K**2:
        break
    
visited = [[-1]*w for _ in range(h)]

def BFS(sy,sx):
    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 j,k in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_y,new_x = y+j,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,BFS(i,j))

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import heapq as hq
H,W,K = map(int,input().split())
A = []
X,Y=0,1
start = None
for h in range(H):
    tmp = list(input())
    A.append(tmp)
    if "S" in tmp:
        start = (tmp.index("S"), h)

def minCost(x,y):
    return min(start[X], W-1-start[X], start[Y], H-1-start[Y]) // K
search = []
searched = [[False for w in range(W)] for h in range(H)]
search.append((start[X],start[Y], 0))
vector = [(1,0),(-1,0),(0,1),(0,-1)]
max_x,min_x,max_y,min_y = 0,W-1,0,H-1
while len(search) > 0:
    x,y,cnt = search.pop()
    if searched[y][x]:
        continue
    searched[y][x] = True
    max_x = max(max_x, x)
    min_x = min(min_x, x)
    max_y = max(max_y, y)
    min_y = min(min_y, y)
    for v in vector:
        newX,newY = x+v[X], y+v[Y]
        if not searched[newY][newX] and cnt < K and A[newY][newX] != "#":
            search.append((newX,newY,cnt+1))

dist = min(min_x, min_y, W-1-max_x, H-1-max_y)
print(1 + (dist+K-1)//K)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
b=[]
v=[[0]*w for _ in range(h)]
sh=0
sw=0
for i in range(h):
    s=list(input())
    b.append(s)
    
    if 'S' in s:
        sh=i
        sw=s.index('S')
#ans=10**18
d=[[0,1],[1,0],[-1,0],[0,-1]]

def bfs(y,x):
    ans=10**18
    c=0
    q=[(y,x)]
    v[y][x]=1
    while c<k:
        p=[]
        c+=1
        for i,j in q:
            for di,dj in d:
                if v[i+di][j+dj]!=1 and b[i+di][j+dj]!='#' and 0<=i+di<h and 0<=j+dj<w:
                    p.append((i+di,j+dj))
                    v[i+di][j+dj]=1
                    ans=min(ans,i+di,j+dj,h-1-i-di,w-1-j-dj)
        q=p
    return ans
ans=bfs(sh,sw)
print(1+(ans+k-1)//k)
#print(b,sh,sw)
#print(v)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
b=[]
v=[[0]*w for _ in range(h)]
sh=0
sw=0
for i in range(h):
    s=list(input())
    b.append(s)
    
    if 'S' in s:
        sh=i
        sw=s.index('S')
#ans=10**18
d=[[0,1],[1,0],[-1,0],[0,-1]]

def bfs(y,x):
    ans=10**18
    c=0
    q=[(y,x)]
    v[y][x]=1
    while c<k:
        p=[]
        c+=1
        for i,j in q:
            for di,dj in d:
                if v[i+di][j+dj]!=1 and b[i+di][j+dj]!='#':
                    p.append((i+di,j+dj))
                    v[i+di][j+dj]=1
                    ans=min(ans,i+di,j+dj,h-1-i-di,w-1-j-dj)
        q=p
    return ans
ans=bfs(sh,sw)
print(1+(ans+k-1)//k)
#print(b,sh,sw)
#print(v)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

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

h,w,k=map(int,input().split())
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s='#'+input().strip()+'#'
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j
    MAP.append(list(s))
MAP.append(A)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
P=[]
Visited=[[False]*(w+2) for _ in range(h+2)]
Visited[sx][sy]=True
q=deque()
q.append((sx,sy,k))
while q:
    x,y,t=q.popleft()
    if t<0:
        break
    P.append([x,y])
    t-=1
    for dx,dy in delta:
        if MAP[y+dy][x+dx]=='.' and not Visited[x+dx][y+dy]:
            q.append((y+dy,x+dx,t))
            Visited[x+dx][y+dy]=True
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

h,w,k=map(int,input().split())
MAP=[]
for i in range(h):
    s=list(input().strip())
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i,j
    MAP.append(s)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
q=deque()
q.append((sx,sy,k))
dist=float('inf')
Visited=[[False]*w for _ in range(h)]
Visited[sy][sx]=True
while len(q)>0:
    x,y,t=q.popleft()
    dist=min(dist,x,y,h-1-x,w-1-y)
    if dist==0:
        break
    if t>0:
        t-=1
        for dx,dy in delta:
            if MAP[x+dx][y+dy]=='.' and not Visited[x+dx][y+dy]:
                q.append((x+dx,y+dy,t))
                Visited[x+dx][y+dy]=True
print(1+ceil(dist/k))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

h,w,k=map(int,input().split())
MAP=[]
for i in range(h):
    s=list(input().strip())
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i,j
    MAP.append(s)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
q=deque()
q.append((sx,sy,k))
dist=float('inf')
Visited=[[False]*w for _ in range(h)]
Visited[sy][sx]=True
while q:
    x,y,t=q.popleft()
    dist=min(dist,x,y,w-1-x,h-1-y)
    if not dist:
        break
    if t:
        t-=1
        for dx,dy in delta:
            if MAP[x+dx][y+dy]=='.' and not Visited[x+dx][y+dy]:
                q.append((x+dx,y+dy,t))
                Visited[x+dx][y+dy]=True
print(1+ceil(dist/k))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

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

h,w,k=map(int,input().split())
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s='#'+input().strip()+'#'
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j
    MAP.append(list(s))
MAP.append(A)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
P=[]
q=deque()
q.append((sx,sy,k))
while q:
    x,y,t=q.popleft()
    if t<0:
        break
    P.append([x,y])
    t-=1
    for dx,dy in delta:
        if MAP[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx,t))
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

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

h,w,k=map(int,input().split())
delta=[[1,0],[0,1],[-1,0],[0,-1]]
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s='#'+input().strip()+'#'
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j
    MAP.append(list(s))
MAP.append(A)
d=[[-1]*(w+2) for _ in range(h+2)]
d[sy][sx]=0
P=[]
q=deque()
q.append((sx,sy))
while q:
    x,y=q.popleft()
    if d[x][y]>k:
        break
    P.append([x,y])
    for dx,dy in delta:
        if d[y+dy][x+dx]==-1 and MAP[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]=d[y][x]+1
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

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

h,w,k=map(int,input().split())
delta=[[1,0],[0,1],[-1,0],[0,-1]]
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s=input()
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j+1
    MAP.append(list(s))
MAP.append(A)
d=[[-1]*(w+2) for _ in range(h+2)]
d[sy][sx]=0
P=[]
q=deque()
q.append((sx,sy))
while q:
    x,y=q.popleft()
    if d[x][y]>k:
        break
    P.append([x,y])
    for dx,dy in delta:
        if d[y+dy][x+dx]==-1 and MAP[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]=d[y][x]+1
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

Submission status: Runtime Error

Solution code:
#h,w,k=map(int, input().split())
#s=[list(input()) for i in range(h)]
p=[[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=='S':
            sta=(i,j)
np=[(1,0),(-1,0),(0,1),(0,-1)]
q={sta}
p[sta[0]][sta[1]]=0
step=0
while step<k and q:
    step+=1
    now=q.pop()
    for i,j in np:
        nx,ny=now[0]+i,now[1]+j
        if nx<0 or nx==h or ny<0 or ny==w:continue
        if s[nx][ny]=='.' and p[nx][ny]==-1:
            p[nx][ny]=step
            q.add((nx,ny))
ans=10**9
for i in range(h):
    for j in range(w):
        if p[i][j]>=0:
            ans=min(ans,i,j,h-i,w-j)
print(-(-ans//k)+1)

Submission status: Runtime Error

Solution code:
# https://beta.atcoder.jp/contests/agc014/submissions/1268295
import sys

input = sys.stdin.readline().rstrip()


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]
    visited = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    q = [(sy, sx, 0)]
    t = max(W, H)
    n = 1
    i = 0
    while n > 0:
        r, c, k = q[i]
        n -= 1
        visited[r][c] = True

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

        if t == 0:
            print(1)
            return

        for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                q.append((nr, nc, k + 1))
                n += 1
        i += 1

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def start_pos():
    for r in range(H):
        for c in range(W):
            if a[r][c] == 'S':
                return r, c
    return -1, -1


def shortest_len(y, x):
    return min(y, H - 1 - y, x, W - 1 - x)


def dfs(y, x, k):
    global need_len
    if b[y][x]: return
    b[y][x] = True
    if not (0 <= y < H and 0 <= x < W): return
    if a[y][x] == '#': return
    need_len = min(need_len, shortest_len(y, x))
    if k == 0: return
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        dfs(y + dy, x + dx, k - 1)


H, W, K = map(int, input().split())
a = [input() for _ in range(H)]
b = [[False for _ in range(W)] for _ in range(H)]
sy, sx = start_pos()
need_len = shortest_len(sy, sx)
dfs(sy, sx, K)

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

'''
最初の魔法で、K回移動で到達できる範囲で、最も壁に近い場所まで移動する
以後、魔法を使用する毎に壁までの最短距離をKずつ移動する
壁に到達したら終了
'''

Submission status: Runtime Error

Solution code:
def start_pos():
    for r in range(H):
        for c in range(W):
            if a[r][c] == 'S':
                return r, c
    return -1, -1


def shortest_len(y, x):
    return min(y, H - 1 - y, x, W - 1 - x)


def dfs(y, x, k):
    global need_len
    if not(0 <= y < H and 0 <= x < W): return
    if a[y][x] == '#': return
    need_len = min(need_len, shortest_len(y, x))
    if k == 0: return
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        dfs(y + dy, x + dx, k - 1)


H, W, K = map(int, input().split())
a = [input() for _ in range(H)]
sy, sx = start_pos()
need_len = shortest_len(sy, sx)
dfs(sy, sx, K)

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

'''
最初の魔法で、K回移動で到達できる範囲で、最も壁に近い場所まで移動する
以後、魔法を使用する毎に壁までの最短距離をKずつ移動する
壁に到達したら終了
'''

Submission status: Runtime Error

Solution code:
h,w,k = map(int,input().split())
a = []
for i in range(h):
  b = input()
  tmp = []
  for j in range(w):
    tmp.append(b[j])
    if b[j] == "S":
      sx = i
      sy = j
  a.append(tmp)
ma = [[0]*w for i in range(h)]
def dfs(x,y):
  if ma[x][y] == 1:
    return
  ma[x][y] = 1
  if x > 0 and a[x-1][y]== ".":
    dfs(x-1,y)
  if y > 0 and a[x][y-1]== ".":
    dfs(x,y-1)
  if x <h-1 and a[x+1][y]==".":
    dfs(x+1,y)
  if y <w-1 and a[x][y+1]==".":
    dfs(x,y+1)
dfs(sx,sy)
ans = float("inf")
for i in range(h):
  for j in range(w):
    if ma[i][j] == 1:
      ans = min(ans,1+(h-i-1)//k+ (1 if (h-i-1)%k else 0),1+(w-j-1)//k+ (1 if (w-j-1)%k else 0),
               1+(i)//k+ (1 if (i)%k else 0),1+(j)//k+ (1 if (j)%k else 0))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque;h,w,k=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];r=9**20
for i in range(h):
 if'S'in m[i]:j=m[i].index('S');q=deque([[i,j]])v[i][j]=0
while q:
 y,x=q.popleft()
 r=min(r,y,x,h-1-y,w-1-x)
 if v[y][x]==k:continue
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t>=0and t<h and u>=0and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
//#include <math.h>
using namespace std;

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> PP;

struct edge {
	int to, cost;
	edge(int t,int c):to(t),cost(c) {}
};
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

//-----------------------------------------------------------------------------

int H,W,K;
string A[800];
int sx,sy;
bool used[800][800];

bool ok(int x,int y) {
	return (x>=0&&x<W&&y>=0&&y<H&&A[y][x]!='#'&&!used[y][x]);
}

int calc(int y,int x) {
	return min(min(x,y),min(W-x-1,H-y-1));
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin>>H>>W>>K;
	REP(i,H) {
		cin>>A[i];
		REP(j,W) if(A[i][j]=='S') sx=j,sy=i;
	}
	queue<P> Q;
	Q.push(P(sx,sy));
	used[sy][sx]=true;
	REP(i,K+1) {
		int sz=Q.size();
		REP(j,sz) {
			P p=Q.front();Q.pop();
			REP(d,4) {
				int nx=p.fi+dx[d],ny=p.se+dy[d];
				if(ok(nx,ny)) {
					used[ny][nx]=true;
					Q.push(P(nx,ny));
				}
			}
		}
	}
	int ans=INF;
	REP(i,H) {
		REP(j,W) {
			if(used[i][j]) ans=min(ans,calc(i,j));
		}
 	}

	cout<<(ans/K)+!!(ans%K)+1<<endl;

	return 0;
}

Submission status: Runtime Error

Solution code:
def Solve():
	H, W, K = [int(i) for i in input().split()]
	S = (0,0)
	A = [[0] * W for i in range(H)]
	for iy in range(H):
		a = input()
		for ix in range(W):
			if a[ix] == "S":
				S = (ix, iy)
				A[iy][ix] = 0
			elif a[ix] == "#":
				A[iy][ix] = 1
			elif a[ix] == ".":
				A[iy][ix] = 0
	def recursive(p):
		for c in [(p[0] + 1, p[1]),(p[0] - 1, p[1]),(p[0], p[1] + 1),(p[0], p[1] - 1),]:
			if A[c[0]][c[1]] == 0:
				if 0 < c[0] < H - 1 and 0 < c[1] < W - 1:
					A[c[0]][c[1]] = -1
					if recursive(c):
						return True
				else:
					return True
		return False
	if recursive(S):
		print(1)
	else:
		print(2)
Solve()

Submission status: Runtime Error

Solution code:
def Solve():
	H, W, K = [int(i) for i in input().split()]
	S = (0,0)
	A = [[0] * W for i in range(H)]
	for iy in range(H):
		a = input()
		for ix in range(W):
			if a[ix] == "S":
				S = (ix, iy)
				A[iy][ix] = 0
			elif a[ix] == "#":
				A[iy][ix] = 1
			elif a[ix] == ".":
				A[iy][ix] = 0
	def recursive(p):
		for c in [(p[0] + 1, p[1]),(p[0] - 1, p[1]),(p[0], p[1] + 1),(p[0], p[1] - 1),]:
			if A[c[0]][c[1]] == 0:
				if 0 < c[0] < H - 1 and 0 < c[1] < W - 1:
					A[c[0]][c[1]] = -1
					if recursive(c):
						return True
				else:
					return True
		return False
	print(S)
	if recursive(S):
		print(1)
	else:
		print(2)
Solve()

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
PAD = '_'
A = [PAD + input() + PAD for _ in range(H)]
A = [PAD * (W + 2)] + A + [PAD * (W + 2)]
V = [[False for _ in range(W + 2)] for _ in range(H + 2)]

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


def __opt_start(pos, vec, k):
    pi, pj = pos
    score = 0
    V[pi][pj] = True
    if k == 0:
        score = __score(pos, vec)
        return pos, vec, score

    opt, optvec, optscore = pos, vec, score
    if (not V[pi - 1][pj]) and pi - 1 >= 1 and A[pi - 1][pj] != '#':
        p, v, s = __opt_start((pi - 1, pj), (-1, 0), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    if (not V[pi + 1][pj]) and pi + 1 <= H and A[pi + 1][pj] != '#':
        p, v, s = __opt_start((pi + 1, pj), (+1, 0), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    if (not V[pi][pj - 1]) and pj - 1 >= 1 and A[pi][pj - 1] != '#':
        p, v, s = __opt_start((pi, pj - 1), (0, -1), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    if (not V[pi][pj + 1]) and pj + 1 <= W and A[pi][pj + 1] != '#':
        p, v, s = __opt_start((pi, pj + 1), (0, +1), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    return opt, optvec, optscore


def __score(pos, vec):
    vi, vj = vec
    i, j = pos
    if vec == (0, 1):
        return W - j
    elif vec == (0, -1):
        return j - 1
    elif vec == (1, 0):
        return H - i
    elif vec == (-1, 0):
        return i - 1
    else:
        return None


def __mahou(sta, vec):
    mahou = 1
    pi, pj = sta
    goal = pi == 1 or pi == H or pj == 1 or pj == W
    while not goal:
        vi, vj = vec
        k = K
        ri, rj = pi + vi, pj + vj
        while k > 0 and not(ri == 0 or ri == H + 1 or rj == 0 or rj == W + 1):
            if A[ri][rj] == '#':
                A[ri] = A[ri][:rj] + '.' + A[ri][rj + 1:]
                k -= 1
            ri, rj = ri + vi, rj + vj

        mahou += 1
        k = K
        while k > 0 and A[pi + vi][pj + vj] != '#':
            pi, pj = pi + vi, pj + vj
            goal = pi == 1 or pi == H or pj == 1 or pj == W
            if goal:
                break
            k -= 1

    return mahou

sta, vec, score = __opt_start(S, None, K)
if vec is None:
    l, r, u, d = (S[0] - 1, W - S[0], S[1] - 1, H - S[1])
    m = min([l, r, u, d])
    if l == m:
        vec = (-1, 0)
    elif r == m:
        vec = (+1, 0)
    elif u == m:
        vec = (0, -1)
    elif d == m:
        vec = (0, +1)
ans = __mahou(sta, vec)
print(ans)