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

Solution (Python):
def solve():
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]

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

    def find2D(Sss, ch):
        for x, Ss in enumerate(Sss):
            y = Ss.find(ch)
            if y != -1:
                return (x, y)
        return (-1, -1)

    xS, yS = find2D(Ass, 'S')

    usedss = [[False]*(W+2) for _ in range(H+2)]
    usedss[xS][yS] = True
    vs = set([(xS, yS)])
    for _ in range(K):
        v2s = set()
        for x, y in vs:
            for dx, dy in dxys:
                x2, y2 = x+dx, y+dy
                if not usedss[x2][y2] and Ass[x2][y2] == '.':
                    usedss[x2][y2] = True
                    v2s.add((x2, y2))
        vs = v2s

    ans = 10**5
    for x in range(H):
        for y in range(W):
            if usedss[x+1][y+1]:
                dist = min(x, H-1-x, y, W-1-y)
                ans = min(ans, -(-dist//K)+1)
    print(ans)

solve()

Solution (Python):
from collections import deque
from math import ceil

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


si, sj = next(
    (i, j)
    for i in range(H)
    for j in range(W)
    if A[i][j] == 'S'
)
q = deque()
q.append((si, sj, 0))
T = {(si, sj)}
while q:
    i, j, d = q.popleft()
    if d < K:
        for x, y in (
                (u, v)
                for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
                if 0 <= u < H and 0 <= v < W and
                A[u][v] == '.' and (u, v) not in T
        ):
            q.append((x, y, d + 1))
            T.add((x, y))
ans = 1 + ceil(
    min(
        min(i, j, H - 1 - i, W - 1 - j)
        for i, j in T
    ) / K
)

print(ans)

Solution (Python):


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)]
hq.heapify(search)
search.append((0, start[X], start[Y]))
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:
    cnt,x,y = hq.heappop(search)
    if x == 0 or x == W-1 or y == 0 or y == H-1:
        print(1)
        exit()
    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] != "
            hq.heappush(search,(cnt+1,newX,newY))
dist = min(min_x, min_y, W-1-max_x, H-1-max_y)
print(1 + (dist+K-1)//K)

Solution (Python):
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')

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
    ans=min(y,x,h-1-y,w-1-x)
    while c<k:
        p=[]
        c+=1
        for i,j in q:
            for di,dj in d:
                if 0<=i+di<h and 0<=j+dj<w and 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)

Solution (Python):
from collections import deque

def main():
    H, W, K = map(int, input().split())
    A = [input() for _ in range(H)]
    s = None
    for i in range(H):
        for j in range(W):
            if A[i][j] == "S":
                s = (i, j)
    q = deque()
    q.append((s[0], s[1], K))
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False] * W for _ in range(H)]
    visited[s[0]][s[1]] = True
    dst = float("inf")
    while(len(q)):
        i, j, m = q.popleft()
        dst = min(dst, min([i, j, H-1-i, W-1-j]))
        if m == 0:
            continue
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni < H and 0 <= nj < W:
                if A[ni][nj] == "." and not visited[ni][nj]:
                    q.append((ni, nj, m-1))
                    visited[ni][nj] = True
    ans = 1 - (-dst//K)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import math
h, w, k = [int(item) for item in input().split()]
field = ["O" * (w+2)]
for i in range(h):
    line = "O" + input().rstrip() + "O"
    field.append(line)
    if "S" in line:
        start = [i+1, line.index("S"), 0]
field.append("O" * (w+2))

dq = deque()
dq.append(start)
visited = [[0] * (w+2) for _ in range(h+2)]
visited[start[0]][start[1]] = 1
closest = 10**3 
while dq:
    x, y, d = dq.popleft()
    closest = min(closest, min(x-1, y-1, h-x, w-y))
    if closest == 0:
        break
    d += 1
    for dx, dy in [[1,0], [0,1], [-1,0], [0,-1]]:
        if field[x+dx][y+dy] == "." and visited[x+dx][y+dy] == 0 and d <= k:
            dq.append([x+dx, y+dy, d])
            visited[x+dx][y+dy] = 1
print(1 + int(math.ceil(closest / k)))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                A[nh][nw] = '
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                A[nh][nw] = '
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    if A[h][w] == '
        continue
    A[h][w] = '
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W:
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == 'S':
        break
visited = A
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
sH = set([h])
sW = set([w])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and visited[h][w] != '
        visited[h][w] = '
        sH.add(h)
        sW.add(w)
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 +
      math.ceil(min([min(sH), H - 1 - max(sH),
                     min(sW), W - 1 - max(sW)]) / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == 'S':
        break
visited = [['.'] * W for _ in range(H)]
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
sH = set([h])
sW = set([w])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and visited[h][w] != '
        visited[h][w] = '
        sH.add(h)
        sW.add(w)
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 +
      math.ceil(min([min(sH), H - 1 - max(sH),
                     min(sW), W - 1 - max(sW)]) / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == 'S':
        break
visited = [['.'] * W for _ in range(H)]
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
sH = set([h])
sW = set([w])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and visited[h][w] != '
        visited[h][w] = '
        sH.add(h)
        sW.add(w)
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 +
      math.ceil(min([min(sH), H - 1 - max(sH),
                     min(sW), W - 1 - max(sW)]) / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        break
visited = [[False] * W for _ in range(H)]
ans = min([i, H - 1 - i, j, W - 1 - j])
Q = collections.deque([[i, j, K]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and not visited[h][w] and A[h][w] == '.':
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res]]
            Q += [[h + 1, w, res]]
            Q += [[h, w - 1, res]]
            Q += [[h, w + 1, res]]
print(1 + math.ceil(ans / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        break
visited = [[False] * W for _ in range(H)]
ans = float('inf')
Q = collections.deque([[i, j, K]])
while Q:
    h, w, res = Q.popleft()
    if A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            if h:
                Q += [[h - 1, w, res]]
            if h < H - 1:
                Q += [[h + 1, w, res]]
            if w:
                Q += [[h, w - 1, res]]
            if w < W - 1:
                Q += [[h, w + 1, res]]
print(1 + math.ceil(ans / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        break
visited = [[False] * W for _ in range(H)]
ans = float('inf')
Q = collections.deque([[i, j, K]])
while Q:
    h, w, res = Q.popleft()
    if not visited[h][w] and A[h][w] == '.':
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            if h:
                Q += [[h - 1, w, res]]
            if h < H - 1:
                Q += [[h + 1, w, res]]
            if w:
                Q += [[h, w - 1, res]]
            if w < W - 1:
                Q += [[h, w + 1, res]]
print(1 + math.ceil(ans / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        break
visited = [[False] * W for _ in range(H)]
ans = min([i, H - 1 - i, j, W - 1 - j])
Q = collections.deque([[i, j, K]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and not visited[h][w] and A[h][w] == '.':
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res]]
            Q += [[h + 1, w, res]]
            Q += [[h, w - 1, res]]
            Q += [[h, w + 1, res]]
print(1 + math.ceil(ans / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == 'S':
        break
visited = [[False] * W for _ in range(H)]

res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
sH = set([h])
sW = set([w])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        
        sH.add(h)
        sW.add(w)
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]

print(1 +
      math.ceil(min([min(sH), H - 1 - max(sH),
                     min(sW), W - 1 - max(sW)]) / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == 'S':
        break
visited = [[False] * W for _ in range(H)]
ans = min([h, H - 1 - h, w, W - 1 - w])
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 + math.ceil(ans / K))

Solution (Python):
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h in range(H):
    if 'S' in A[h]:
        w = A[h].index('S')
        break
visited = [[False] * W for _ in range(H)]
ans = min([h, H - 1 - h, w, W - 1 - w])
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 + math.ceil(ans / K))

Solution (Python):
from collections import deque
from math import ceil
import sys
def input():
	return sys.stdin.readline()[:-1]

H, W, k = map(int, input().split())
m = [input() for _ in range(H)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[10**10 for _ in range(W)] for _ in range(H)]

for h in range(1, H-1):
	for w in range(1, W-1):
		if m[h][w] == "S":
			q.appendleft([h, w])
			sx, sy = h, w

step[sx][sy] = 0
while q:
	label = q.pop()
	if step[label[0]][label[1]] == k:
		continue
	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if 0 <= h < H and 0 <= w < W:
			if m[h][w] == "." and step[h][w] > step[label[0]][label[1]] + 1:
				q.appendleft([h, w])
				step[h][w] = step[label[0]][label[1]] + 1

min_dis = max(H, W)
for h in range(H):
	for w in range(W):
		if step[h][w] <= k:
			min_dis = min(min_dis, h, w, H-h-1, W-w-1)

print(1+ceil(min_dis/k))

Solution (Python):
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[sx][sy]=True
while q:
    x,y,t=q.popleft()
    dist=min(dist,x,y,h-1-x,w-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))

Solution (Python):
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[sx][sy]=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))

Solution (Python):
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
    nq=set()
    while q:
        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
                nq.add((nx,ny))
    q=nq.copy()

ans=10**9
for i in range(h):
    for j in range(w):
        if p[i][j]>=0:
            an=min(i,j,h-i-1,w-j-1)
            if ans>an:ans=an
print(-(-ans//k)+1)

Solution (Python):
from collections import deque
from math import ceil
H,W,K=map(int,input().split())
grid=[input() for i in range(H)]

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

stack=deque([(S[0],S[1],0)])
visited=[[False]*(W) for i in range(H)]
visited[S[0]][S[1]]=True
a=float("inf")
t=[-1,1]
while stack:
  i,j,m=stack.popleft()
  if m>K:
    break
  a=min(a,min(i,H-1-i,j,W-1-j))
  if a==0:
    break
  for s in t:
    if not visited[i+s][j] and grid[i+s][j]!="
      stack.append((i+s,j,m+1))
    if not visited[i][j+s] and grid[i][j+s]!="
      stack.append((i,j+s,m+1))
    visited[i+s][j]=True
    visited[i][j+s]=True
ans=1+ceil(a/K)
print(ans)

Solution (Python):

from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[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

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        
        if t == 0:
            print(1)
            return

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
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,z):
  if ma[x][y] == 1:
    return
  if z>k:
    return
  ma[x][y] = 1
  if x > 0 and a[x-1][y]== ".":
    que.append([x-1,y,z+1])
  if y > 0 and a[x][y-1]== ".":
    que.append([x,y-1,z+1])
  if x <h-1 and a[x+1][y]==".":
    que.append([x+1,y,z+1])
  if y <w-1 and a[x][y+1]==".":
    que.append([x,y+1,z+1])
que = deque([[sx,sy,0]])
while que:
  x,y,z = que.popleft()
  dfs(x,y,z)
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)

Solution (Python):
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)
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0and v[y][x]<k:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Solution (Python):
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)
 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]<0and v[y][x]<k:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Solution (Python):
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)
 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]<0and v[y][x]<k:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Solution (Python):
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))

Solution (Python):
def solve():
    from collections import deque
    h, w, k = map(int, input().split())
    maze = [input() for _ in range(h)]
    visited = [[-1]*w for _ in range(h)]
    for i in range(h):
        if 'S' in maze[i]:
            sy, sx = i, maze[i].index('S')
            break
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    r = 10**18
    while queue:
        y, x = queue.popleft()
        r = min(r, y, h-1-y, x, w-1-x)
        if visited[y][x] == k: continue
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w: continue
            if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    print(1 -(-r // k))
if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    from collections import deque
    h, w, k = map(int, input().split())
    maze = [input() for _ in range(h)]
    visited = [[-1]*w for j in range(h)]
    for i in range(h):
        if 'S' in maze[i]:
            sy, sx = i, maze[i].index('S')
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    r = 10**18
    while queue:
        y, x = queue.popleft()
        r = min(r, y, x, h-1-y, w-1-x)
        if visited[y][x] == k: continue
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if new_y < 0 or new_y >= h: continue
            if new_x < 0 or new_x >= w: continue
            if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    print(1 -(-r // k))
if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
h, w, k = map(int, input().split())
maze = [input() for _ in range(h)]
visited = [[-1]*w for j in range(h)]
for i in range(h):
    if 'S' in maze[i]:
        sy, sx = i, maze[i].index('S')
queue = deque([[sy, sx]])
visited[sy][sx] = 0
r = 10**18
while queue:
    y, x = queue.popleft()
    r = min(r, y, x, h-1-y, w-1-x)
    if visited[y][x] == k: continue
    for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+i, x+j
        if new_y < 0 or new_y >= h: continue
        if new_x < 0 or new_x >= w: continue
        if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
            visited[new_y][new_x] = visited[y][x] + 1
            queue.append([new_y, new_x])
print(1 -(-r // k))

Solution (Python):
h, w, k=map(int, raw_input().split())
a=["
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

Solution (Python):
from collections import deque

H,W,K = map(int,input().split())
src = [input() for i in range(H)]
sx = sy = None
for i,row in enumerate(src):
    if 'S' in row:
        sy = i
        sx = row.index('S')

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
visited = [[0]*W for i in range(H)]
visited[sy][sx] = 1
q = deque([(0,sx,sy)])
mindist = H+W
while q:
    d,x,y = q.popleft()
    if d > K: break
    dist = min(x, W-x-1, y, H-y-1)
    mindist = min(dist, mindist)
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if src[ny][nx] == '
        if visited[ny][nx]: continue
        q.append((d+1,nx,ny))
        visited[ny][nx] = 1

ans = -(-mindist//K) + 1
print(ans)

Solution (Python):
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()

Solution (Python):
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)