AtCoder Grand Contest 014 - Closed Rooms

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.

Examples

Input

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


Output

1


Input

3 3 3
.#
S.


Output

1


Input

3 3 3

S#


Output

2


Input

7 7 2


...##
S###
.#.##
.###


Output

2

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

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


from collections import deque
INF = float('inf')
(H, W, K) = map(int, input().split())
A = [list(input()) for _ in range(H)]
(Si, Sj) = (0, 0)
for (i, a) in enumerate(A):
	if 'S' in a:
		(Si, Sj) = (i, a.index('S'))
		A[Si][Sj] = 'c'
		break
distance = INF
Q = deque([(0, Si, Sj)])
while Q:
	(cnt, i, j) = Q.popleft()
	distance = min(distance, i, j, H - i - 1, W - j - 1)
	if cnt >= K:
		continue
	for (ni, nj) in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
		if 0 <= ni < H and 0 <= nj < W and (A[ni][nj] == '.'):
			A[ni][nj] = 'c'
			Q.append((cnt + 1, ni, nj))
print(-(-distance // K) + 1)


import sys
input = sys.stdin.readline

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


from collections import deque
(H, W, K) = map(int, input().split())
chart = [list(input()) for _ in range(H)]
start = (-1, -1)
for h in range(H):
	for w in range(W):
		if chart[h][w] == 'S':
			start = (h, w)
			chart[h][w] = '.'
minDist = [[float('inf')] * W for _ in range(H)]
que = deque([(start[0], start[1], 0)])
while que:
	(nh, nw, dist) = que.popleft()
	if minDist[nh][nw] <= dist:
		continue
	minDist[nh][nw] = dist
	if dist == K:
		continue
	for toH in [nh - 1, nh + 1]:
		if toH < 0 or toH >= H:
			continue
		if chart[toH][nw] == '.':
			que.append((toH, nw, dist + 1))
	for toW in [nw - 1, nw + 1]:
		if toW < 0 or toW >= W:
			continue
		if chart[nh][toW] == '.':
			que.append((nh, toW, dist + 1))
ans = float('inf')
for h in range(H):
	for w in range(W):
		if minDist[h][w] == float('inf'):
			continue
		d = min(h, w, H - h - 1, W - w - 1)
		if d == 0:
			ans = min(ans, 1)
		else:
			ans = min(ans, -(-d // K) + 1)
print(ans)


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


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):
	distance = [[inf] * w for _ in range(h)]

	def bfs():
		queue = deque()
		queue.append(s)
		distance[s[0]][s[1]] = 0
		while len(queue):
			(y, x) = queue.popleft()
			for i in range(4):
				(nx, ny) = (x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i])
				if 0 <= nx < w and 0 <= ny < h and (maze[ny][nx] != '#'):
					if distance[ny][nx] <= distance[y][x] + 1:
						continue
					queue.append((ny, nx))
					distance[ny][nx] = distance[y][x] + 1
		return distance
	return bfs()

def examC():
	(H, W, K) = LI()
	A = [SI() for _ in range(H)]
	sx = W - 1
	sy = H - 1
	for i in range(H):
		for j in range(W):
			if A[i][j] == 'S':
				sy = i
				sx = j
				break
		if sy != H - 1 or sx != W - 1:
			break
	D = clear_maze(H, W, [sy, sx], A)
	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
examC()


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


from collections import deque
(H, W, K) = map(int, input().split())
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
G = [list(input()) for _ in range(H)]
check = [[-1] * W for _ in range(H)]
que = deque()
flag = False
for h in range(H):
	for w in range(W):
		if G[h][w] == 'S':
			que.append((h, w))
			flag = True
			break
	if flag:
		break
x_min = h
x_max = h
y_min = w
y_max = w
check[h][w] = 0
while que:
	tmp = que.popleft()
	x = tmp[0]
	y = tmp[1]
	now_ = check[x][y]
	if now_ == K:
		continue
	for (dx, dy) in move:
		nx = x + dx
		ny = y + dy
		if not (0 <= nx < H and 0 <= ny < W):
			continue
		if G[nx][ny] == '#':
			continue
		if check[nx][ny] == -1:
			check[nx][ny] = now_ + 1
			que.append((nx, ny))
			x_min = min(x_min, nx)
			x_max = max(x_max, nx)
			y_min = min(y_min, ny)
			y_max = max(y_max, ny)
ans = 10 ** 18
ans = min(ans, (x_min + K - 1) // K + 1)
ans = min(ans, (H - x_max - 1 + K - 1) // K + 1)
ans = min(ans, (y_min + K - 1) // K + 1)
ans = min(ans, (W - y_max - 1 + K - 1) // K + 1)
print(ans)


import math
(H, W, K) = map(int, input().split())
A = []
S = [0, 0]
for i in range(H):
	a = list(input())
	for j in range(W):
		if a[j] == 'S':
			S = [i, j]
	A.append(a)
import sys
input = sys.stdin.readline
B = [[1000 for j in range(W)] for i in range(H)]
B[S[0]][S[1]] = 0
ans = min(S[0], S[1], W - 1 - S[1], H - 1 - S[0])
Q = [[0, S[0], S[1]]]
for i in range(10 ** 6):
	if i == len(Q):
		break
	else:
		for j in range(1):
			if Q[i][1] > 0 and B[Q[i][1] - 1][Q[i][2]] == 1000 and (B[Q[i][1]][Q[i][2]] < K) and (A[Q[i][1] - 1][Q[i][2]] == '.'):
				Q.append([Q[i][0] + 1, Q[i][1] - 1, Q[i][2]])
				B[Q[i][1] - 1][Q[i][2]] = B[Q[i][1]][Q[i][2]] + 1
				if ans > min(Q[i][1] - 1, Q[i][2], H - 1 - (Q[i][1] - 1), W - 1 - Q[i][2]):
					ans = min(Q[i][1] - 1, Q[i][2], H - 1 - (Q[i][1] - 1), W - 1 - Q[i][2])
			if Q[i][2] > 0 and B[Q[i][1]][Q[i][2] - 1] == 1000 and (B[Q[i][1]][Q[i][2]] < K) and (A[Q[i][1]][Q[i][2] - 1] == '.'):
				Q.append([Q[i][0] + 1, Q[i][1], Q[i][2] - 1])
				B[Q[i][1]][Q[i][2] - 1] = B[Q[i][1]][Q[i][2]] + 1
				if ans > min(Q[i][1], Q[i][2] - 1, H - 1 - Q[i][1], W - 1 - (Q[i][2] - 1)):
					ans = min(Q[i][1], Q[i][2] - 1, H - 1 - Q[i][1], W - 1 - (Q[i][2] - 1))
			if Q[i][1] < H - 1 and B[Q[i][1] + 1][Q[i][2]] == 1000 and (B[Q[i][1]][Q[i][2]] < K) and (A[Q[i][1] + 1][Q[i][2]] == '.'):
				Q.append([Q[i][0] + 1, Q[i][1] + 1, Q[i][2]])
				B[Q[i][1] + 1][Q[i][2]] = B[Q[i][1]][Q[i][2]] + 1
				if ans > min(Q[i][1] + 1, Q[i][2], H - 1 - (Q[i][1] + 1), W - 1 - Q[i][2]):
					ans = min(Q[i][1] + 1, Q[i][2], H - 1 - (Q[i][1] + 1), W - 1 - Q[i][2])
			if Q[i][2] < W - 1 and B[Q[i][1]][Q[i][2] + 1] == 1000 and (B[Q[i][1]][Q[i][2]] < K) and (A[Q[i][1]][Q[i][2] + 1] == '.'):
				Q.append([Q[i][0] + 1, Q[i][1], Q[i][2] + 1])
				B[Q[i][1]][Q[i][2] + 1] = B[Q[i][1]][Q[i][2]] + 1
				if ans > min(Q[i][1], Q[i][2] + 1, H - 1 - Q[i][1], W - 1 - (Q[i][2] + 1)):
					ans = min(Q[i][1], Q[i][2] + 1, H - 1 - Q[i][1], W - 1 - (Q[i][2] + 1))
print(math.ceil(ans / K) + 1)


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


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)
INF = 10 ** 15

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
(h, w, k) = LI()
A = SRL(h)
q = deque()
for a in range(h):
	if 'S' in A[a]:
		sy = a
		sx = A[a].index('S')
		q += [(sy, sx)]
A[sy][sx] = 0
min_dist = INF
while q:
	(y, x) = q.popleft()
	min_dist = min(min_dist, x, y, h - 1 - y, w - 1 - x)
	for (i, j) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
		(nx, ny) = (x + i, y + j)
		if 0 <= nx < w and 0 <= ny < h and (A[ny][nx] == '.'):
			A[ny][nx] = A[y][x] + 1
			if A[ny][nx] > k:
				continue
			q += [(ny, nx)]
print(1 - -min_dist // k)


import sys
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(buff_readline())

def read_int_n():
	return list(map(int, buff_readline().split()))

def read_float():
	return float(buff_readline())

def read_float_n():
	return list(map(float, buff_readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv(H, W, K, A):
	for i in range(H):
		for j in range(W):
			if A[i][j] == 'S':
				s = (i, j)
	from collections import deque
	q = deque([s])
	d = [[None] * W for _ in range(H)]
	d[s[0]][s[1]] = 0
	ans = INF
	while q:
		(x, y) = q.popleft()
		t = min(abs(x), abs(x - H + 1), abs(y), abs(y - W + 1))
		ans = min(ans, t)
		for (vx, vy) in [(x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y)]:
			if not (0 <= vx < H and 0 <= vy < W):
				continue
			if A[vx][vy] == '#':
				continue
			if d[vx][vy] is not None:
				continue
			c = d[x][y]
			if c + 1 <= K:
				q.append((vx, vy))
				d[vx][vy] = c + 1
	return 1 + -(-ans // K)

def main():
	(H, W, K) = read_int_n()
	A = [read_str() for _ in range(H)]
	print(slv(H, W, K, A))
main()


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)


from collections import deque
import math
(h, w, k) = map(int, input().split())
a = [input() for i in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j] == 'S':
			(sy, sx) = (i, j)
d = deque([[sy, sx]])
dist = []
inf = -1
m = 1000
for i in range(h):
	dist.append([inf] * w)
dist[sy][sx] = 0
while len(d) != 0:
	b = d.popleft()
	(p, q) = (b[0], b[1])
	for i in [[1, 0], [0, -1], [-1, 0], [0, 1]]:
		(by, bx) = (b[0] + i[0], b[1] + i[1])
		if bx >= 0 and bx < w and (by >= 0) and (by < h) and (a[by][bx] != '#') and (dist[by][bx] == -1) and (dist[p][q] < k):
			d.append([by, bx])
			dist[by][bx] = dist[p][q] + 1
for i in range(h):
	for j in range(w):
		if dist[i][j] != -1:
			m = min(m, 0 - -min(i, h - 1 - i, j, w - 1 - j) // k)
print(m + 1)


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


from collections import deque
(h, w, k) = map(int, input().split())
a = [input() for i in range(h)]
INF = 10 ** 9
for i in range(h):
	for j in range(w):
		if a[i][j] == 'S':
			(si, sj) = (i, j)
			break
cnt = [[INF] * w for i in range(h)]
cnt[si][sj] = 0
q = deque([(si, sj, 0)])
while q:
	(pi, pj, cost) = q.popleft()
	for (nxi, nxj) in [(pi + 1, pj), (pi, pj + 1), (pi - 1, pj), (pi, pj - 1)]:
		if not (0 <= nxi < h and 0 <= nxj < w):
			continue
		if a[nxi][nxj] == '.' and cost + 1 < cnt[nxi][nxj] and (cost + 1 <= k):
			cnt[nxi][nxj] = cost + 1
			q.append((nxi, nxj, cost + 1))
ans = 10 ** 9
for i in range(h):
	for j in range(w):
		if cnt[i][j] <= k:
			ans = min(ans, -(-i // k), -(-(h - i - 1) // k), -(-j // k), -(-(w - j - 1) // k))
print(ans + 1)


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
BIG = 10 ** 18
R = 10 ** 9 + 7

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)


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)


from collections import deque
inf = 10 ** 9 + 7
(h, w, k) = map(int, input().split())
a = [list(input()) for i in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j] == 'S':
			(sx, sy) = (i, j)
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
l = [[inf] * w for i in range(h)]
l[sx][sy] = 0
s = set()
s.add((sx, sy))
que = deque([[sx, sy]])
ans = inf
while que:
	(x, y) = que.popleft()
	if x == 0 or x == h - 1 or y == 0 or (y == w - 1):
		ans = 1
		break
	if l[x][y] == k:
		continue
	for i in range(4):
		(nx, ny) = (x + d[i][0], y + d[i][1])
		if nx < 0 or nx >= h or ny < 0 or (ny >= w) or (a[nx][ny] == '#') or (l[nx][ny] != inf):
			continue
		s.add((nx, ny))
		l[nx][ny] = l[x][y] + 1
		que.append([nx, ny])
for i in s:
	c = (min(i[0], h - i[0] - 1, i[1], w - i[1] - 1) + k - 1) // k + 1
	ans = min(ans, c)
print(ans)


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


(h, w, k) = map(int, input().split())
a = [input() for _ in range(h)]
s = (0, 0)
for i in range(h * w):
	(x, y) = divmod(i, w)
	if a[x][y] == 'S':
		s = (x, y)
		break
from collections import deque
todo = deque([s])
inf = float('inf')
seen = [[inf] * w for _ in range(h)]
seen[s[0]][s[1]] = 0
while todo:
	(x, y) = todo.popleft()
	for (dx, dy) in ((0, 1), (0, -1), (1, 0), (-1, 0)):
		nx = x + dx
		ny = y + dy
		if 0 <= nx < h and 0 <= ny < w and (a[nx][ny] != '#') and (seen[nx][ny] > seen[x][y] + 1):
			seen[nx][ny] = seen[x][y] + 1
			if seen[nx][ny] < k:
				todo.append((nx, ny))
ans = h * w
for i in range(h * w):
	(x, y) = divmod(i, w)
	if seen[x][y] == inf:
		continue
	tmp = min(x, y, h - x - 1, w - y - 1)
	tmp = (tmp + k - 1) // k
	ans = min(ans, tmp)
print(ans + 1)


import sys
input = sys.stdin.readline
from collections import deque
(h, w, k) = map(int, input().split())
A = [input().rstrip() for _ in range(h)]
for (i, a) in enumerate(A):
	if 'S' in a:
		sy = i
		sx = a.index('S')
		break
que = deque()
D = ((-1, 0), (0, -1), (1, 0), (0, 1))

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


class Grid:

	def __init__(self, H, W, grid, road_wall=('.', '#')):
		(self.road, self.wall) = road_wall
		self.H = H
		self.W = W
		self.grid = grid
		self.parent = [[0] * self.W for _ in range(self.H)]
		self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

	def bfs(self, start=(0, 0), goal=-3, time=0, save=False):
		if save:
			parent = self.parent
		else:
			parent = [[0] * self.W for _ in range(self.H)]
		(p, t) = (start, time)
		parent[p[0]][p[1]] = 1
		next_set = deque([(p, t)])
		while next_set:
			(p, t) = next_set.popleft()
			(h, w) = p
			for (dh, dw) in self.move:
				q = (h + dh, w + dw)
				if q[0] < 0 or q[0] >= self.H or q[1] < 0 or (q[1] >= self.W):
					continue
				if self.grid[q[0]][q[1]] == self.wall:
					continue
				if parent[q[0]][q[1]] != 0:
					continue
				if t >= K:
					continue
				if q == goal:
					return t + 1
				parent[q[0]][q[1]] = 1
				next_set.append((q, t + 1))
		return parent

	def debug(self, start, goal, p, t):
		player = p
		debug_grid = list((list(self.grid[h]) for h in range(self.H)))
		if start != (None, None):
			debug_grid[start[0]][start[1]] = 'S'
		if goal != -3:
			debug_grid[goal[0]][goal[1]] = 'G'
		debug_grid[player[0]][player[1]] = 'P'
		print('~~~~~~~~~ t = ' + str(t + 1) + '  ~~~~~~~~')
		for debug_h in range(self.H):
			print(''.join((str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W))))
from collections import deque
import sys
from math import ceil
import marshal
input = sys.stdin.readline
(road, wall) = ('.', '#')
(H, W, K) = map(int, input().split())
grid = []
for h in range(H):
	grid.append(input().rstrip())
	for (w, s) in enumerate(grid[-1]):
		if s == 'S':
			start = (h, w)
g = Grid(H, W, grid, (road, wall))
visit = g.bfs(start=start)
res = float('inf')
for h in range(H):
	for w in range(W):
		if visit[h][w]:
			res = min(ceil(h / K) + 1, ceil(w / K) + 1, ceil((H - 1 - h) / K) + 1, ceil((W - 1 - w) / K) + 1, res)
print(res)


import sys
input = sys.stdin.readline
import itertools
(H, W, K) = map(int, input().split())
A = '#' * (W + 2)
for _ in range(H):
	A += '#' + input().rstrip() + '#'
A += '#' * (W + 2)
start = A.find('S')
dxs = [1, -1, W + 2, -(W + 2)]
visited = set()
q = [start]
visited.add(start)
for _ in range(K):
	qq = []
	for (dx, x) in itertools.product(dxs, q):
		y = x + dx
		if A[y] == '#':
			continue
		if y in visited:
			continue
		visited.add(y)
		qq.append(y)
	q = qq
nearest = 10 ** 9
for x in visited:
	(row, col) = divmod(x, W + 2)
	d = min(row - 1, H - row, col - 1, W - col)
	if nearest > d:
		nearest = d
answer = 1 + (nearest + K - 1) // K
print(answer)


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


from collections import deque
(H, W, K, *L) = open(0).read().split()
L = [list(a) for a in L]
(H, W, K) = map(int, (H, W, K))
q = deque([])
step = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for (i, a) in enumerate(L):
	if 'S' in a:
		q = deque([(0, i, a.index('S'))])
		break
ans = 10 ** 10
while q:
	(c, a, b) = q.popleft()
	x = min(a, H - a - 1, b, W - b - 1)
	cnt = 1 + (x + K - 1) // K
	ans = min(cnt, ans)
	if c + 1 > K:
		continue
	for (dx, dy) in step:
		n = a + dx
		m = b + dy
		if not (-1 < n < H and -1 < m < W):
			continue
		if L[n][m] == '.':
			L[n][m] = '#'
			q.append((c + 1, n, m))
print(ans)


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)


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


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)


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


from collections import deque
(H, W, K) = map(int, input().split())
A = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
	A_i_x = input()
	for j in range(W):
		A[i][j] = A_i_x[j]
		if A_i_x[j] == 'S':
			start_h = i
			start_w = j
dist_from_exit = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
	for j in range(W):
		dist_from_exit[i][j] = min(i, j, H - 1 - i, W - 1 - j)
queue = deque()
queue.append([start_h, start_w])
visited = [[-1 for _ in range(W)] for _ in range(H)]
visited[start_h][start_w] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
dist_left_cand = [dist_from_exit[start_h][start_w]]
while queue:
	(h, w) = queue.pop()
	for i in range(4):
		if 0 <= h + dy[i] <= H - 1 and 0 <= w + dx[i] <= W - 1:
			if visited[h + dy[i]][w + dx[i]] == -1 and A[h + dy[i]][w + dx[i]] == '.' and (visited[h][w] < K):
				queue.appendleft([h + dy[i], w + dx[i]])
				visited[h + dy[i]][w + dx[i]] = visited[h][w] + 1
				dist_left_cand.append(dist_from_exit[h + dy[i]][w + dx[i]])
dist_left_min = min(dist_left_cand)
print((dist_left_min - 1) // K + 1 + 1)


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


import sys
sys.setrecursionlimit(500000)
from collections import deque
INF = float('inf')
(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)
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
R = [[INF] * W for _ in range(H)]
R[sx][sy] = 0
reach = set([])
reach.add((sx, sy))
Q = deque([[sx, sy]])
while Q:
	(x, y) = Q.popleft()
	if x == 0 or x == H - 1 or y == 0 or (y == W - 1):
		print(1)
		exit()
	if R[x][y] == K:
		continue
	for i in range(4):
		nx = x + d[i][0]
		ny = y + d[i][1]
		if nx < 0 or nx >= H or ny < 0 or (ny >= W) or (Room[nx][ny] == '#') or (R[nx][ny] != INF):
			continue
		reach.add((nx, ny))
		R[nx][ny] = R[x][y] + 1
		Q.append([nx, ny])
ans = INF
for t in reach:
	(x, y) = (t[0], t[1])
	nokori = min(x, H - 1 - x, y, W - 1 - y)
	step = (nokori + K - 1) // K + 1
	ans = min(ans, step)
print(ans)


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


from collections import deque
(h, w, K) = map(int, input().split())
maze = [[x for x in input()] for _ in range(h)]
sx = 0
sy = 0
for i in range(h):
	for j in range(w):
		if maze[i][j] == 'S':
			sx = j
			sy = i
d = [[float('inf')] * w for _ in range(h)]
d[sy][sx] = 0
q = deque([[sy, sx]])
c = 0
visited = [[False] * w for _ in range(h)]
visited[sy][sx] = True
while q:
	(y, x) = q.popleft()
	for (j, k) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
		(ny, nx) = (y + j, x + k)
		if maze[ny][nx] == '.' and (not visited[ny][nx]):
			d[ny][nx] = d[y][x] + 1
			if ny in {0, h - 1} or nx in {0, w - 1}:
				if d[ny][nx] <= K:
					print(1)
					exit()
				else:
					continue
			else:
				visited[ny][nx] = True
				if d[ny][nx] == K:
					continue
				else:
					q.append([ny, nx])

def BFS(sy, sx):
	visited = [[-1] * w for _ in range(h)]
	q = deque([[sy, sx]])
	visited[sy][sx] = 0
	while q:
		(y, x) = q.popleft()
		if y == 0 or y == h - 1 or x == 0 or (x == w - 1):
			return visited[y][x]
		for (l, k) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
			(new_y, new_x) = (y + l, x + k)
			if visited[new_y][new_x] == -1:
				visited[new_y][new_x] = visited[y][x] + 1
				q.append([new_y, new_x])
ans = float('inf')
for i in range(h):
	for j in range(w):
		if d[i][j] <= K:
			ans = min(ans, min(i, h - 1 - i, j, w - 1 - j))
print((ans - 1) // K + 2)


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


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


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


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

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)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def A():

	def f(n):
		return ((1 << n) - (1 - 2 * (n & 1))) // 3

	def k(x, n):
		return f(n) * s + (1 - 2 * (n & 1)) * x
	a = LI()
	if a[0] % 2 or a[1] % 2 or a[2] % 2:
		print(0)
		return
	if a[0] == a[1] == a[2]:
		print(-1)
		return
	s = sum(a)
	ans = 10 ** 5
	for i in range(3):
		l = 0
		r = 10 ** 5 + 1
		while r - l > 1:
			m = l + r >> 1
			ka = k(a[i], m)
			if ka & (1 << m) - 1 == 0:
				l = m
			else:
				r = m
		ans = min(ans, l)
	print(ans)
	return

def B():
	(n, m) = LI()
	f = [0] * n
	for i in range(m):
		(a, b) = LI()
		f[a - 1] ^= 1
		f[b - 1] ^= 1
	if all([not f[i] % 2 for i in range(n)]):
		print('YES')
	else:
		print('NO')
	return

def C():
	d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
	(h, w, k) = LI()
	a = SR(h)
	for y in range(h):
		for x in range(w):
			if a[y][x] == 'S':
				(sy, sx) = (y, x)
				break
	bfs = [[-1] * w for i in range(h)]
	bfs[sy][sx] = 0
	q = deque([(sy, sx)])
	while q:
		(y, x) = q.popleft()
		for (dy, dx) in d:
			(ny, nx) = (y + dy, x + dx)
			if 0 <= ny < h and 0 <= nx < w:
				if a[ny][nx] == '#':
					continue
				if bfs[ny][nx] < 0:
					bfs[ny][nx] = bfs[y][x] + 1
					if bfs[ny][nx] < k:
						q.append((ny, nx))
	ans = float('inf')
	for y in range(h):
		for x in range(w):
			if bfs[y][x] >= 0:
				ans = min(ans, y, h - 1 - y, x, w - 1 - x)
	print(math.ceil(ans / k) + 1)
	return

def D():
	return

def E():
	return

def F():
	return
C()


from collections import deque
(H, W, K) = map(int, input().split())
A = [input() for _ in range(H)]
(sx, sy) = (0, 0)
for y in range(H):
	flag = False
	for x in range(W):
		if A[y][x] == 'S':
			(sx, sy) = (x, y)
			flag = True
			break
	if flag:
		break
dist = [[-1] * W for _ in range(H)]
dist[sy][sx] = 0
q = deque([(sy, sx)])
while q:
	(y, x) = q.popleft()
	if dist[y][x] == K:
		continue
	for (dx, dy) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
		(nx, ny) = (x + dx, y + dy)
		if 0 <= nx < W and 0 <= ny < H and (dist[ny][nx] == -1) and (A[ny][nx] == '.'):
			dist[ny][nx] = dist[y][x] + 1
			q.append((ny, nx))
ret = float('inf')
for y in range(H):
	for x in range(W):
		if dist[y][x] < 0:
			continue
		ret = min(ret, 1 + (min(H - y, y + 1, W - x, x + 1) - 1 + K - 1) // K)
print(ret)


from collections import deque
(H, W, K) = map(int, input().split())
A = [input() for h in range(H)]
for h in range(H):
	for w in range(W):
		if A[h][w] == 'S':
			(sx, sy) = (h, w)
INF = 1000
dist = [[INF for w in range(W)] for h in range(H)]
dist[sx][sy] = 0
dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
start = []
d = deque([[sx, sy]])
while d:
	(x, y) = d.popleft()
	for (dx, dy) in dxy:
		xx = x + dx
		yy = y + dy
		if 0 <= xx < H and 0 <= yy < W and (dist[xx][yy] == INF):
			if A[xx][yy] == '.':
				dist[xx][yy] = dist[x][y] + 1
				d.append([xx, yy])
				if dist[xx][yy] <= K:
					start.append([xx, yy])
ans = min(-(-(H - 1 - sx) // K) + 1, -(-sx // K) + 1, -(-(W - 1 - sy) // K) + 1, -(-sy // K) + 1)
for (x, y) in start:
	ans = min(ans, -(-(W - 1 - y) // K) + 1)
	ans = min(ans, -(-y // K) + 1)
	ans = min(ans, -(-(H - 1 - x) // K) + 1)
	ans = min(ans, -(-x // K) + 1)
print(ans)


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


import collections as C
(H, W, K) = map(int, input().split())
A = [list(input()) for _ in [0] * H]
for (i, a) in enumerate(A):
	if 'S' in a:
		j = a.index('S')
		Q = C.deque([(1, i, j)])
d = 1000000000.0
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)


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


(h, w, k) = map(int, input().split())
maze = []
for i in range(h):
	maze.append(input())
	for j in range(w):
		if maze[i][j] == 'S':
			(x, y) = (i, j)
ans = float('INF')
l = [[float('INF')] * w for i in range(h)]
l[x][y] = 0
from collections import deque
dq = deque([(x, y)])
p = {(x, y)}
while len(dq):
	(nx, ny) = dq.popleft()
	for (a, s) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
		if 0 <= a + nx < h and 0 <= ny + s < w and (l[a + nx][s + ny] == float('INf')) and (maze[a + nx][s + ny] == '.'):
			l[a + nx][ny + s] = l[nx][ny] + 1
			if l[a + nx][ny + s] <= k:
				p.add((a + nx, s + ny))
			if l[a + nx][ny + s] < k:
				dq.append((a + nx, s + ny))
ans = float('INf')
for (x, y) in p:
	ans = min(ans, (min(x, y, h - 1 - x, w - 1 - y) + k - 1) // k + 1)
print(ans)


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


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)


from collections import deque
(h, w, k) = map(int, input().split())
g = [list(input()) for _ in range(h)]
ans = h * w
for i in range(h):
	if 'S' in g[i]:
		sx = g[i].index('S')
		sy = i
		break
g[sy][sx] = 0
q = deque()
q.append(sy * w + sx)
while q:
	v = q.popleft()
	(y, x) = (v // w, v % w)
	cur = min((y - 1) // k, (x - 1) // k, (h - y - 2) // k, (w - x - 2) // k) + 2
	if ans > cur:
		ans = cur
	if g[y][x] < k:
		for (dx, dy) in ((0, 1), (1, 0), (0, -1), (-1, 0)):
			nx = x + dx
			ny = y + dy
			if 0 <= nx < w and 0 <= ny < h and (g[ny][nx] == '.'):
				g[ny][nx] = g[y][x] + 1
				q.append(ny * w + nx)
print(ans)


def solve():
	dxys = [(-1, 0), (1, 0), (0, -1), (0, 1)]
	(H, W, K) = map(int, input().split())
	Ass = ['#' * (W + 2)] + ['#' + input() + '#' for _ in range(H)] + ['#' * (W + 2)]

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


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


import math
import os
import sys
from collections import deque
if os.getenv('LOCAL'):
	sys.stdin = open('_in.txt', 'r')
sys.setrecursionlimit(2147483647)
INF = float('inf')
IINF = 10 ** 18
MOD = 10 ** 9 + 7
(H, W, K) = list(map(int, sys.stdin.readline().split()))
A = [sys.stdin.readline().rstrip() for _ in range(H)]
sh = sw = -1
for (h, r) in enumerate(A):
	if 'S' in r:
		sh = h
		sw = r.index('S')

def step(h, w):
	return math.ceil(min(h, w, H - h - 1, W - w - 1) / K)

def ok(h, w):
	return 0 <= h < H and 0 <= w < W
dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]
que = deque([(sh, sw, K)])
seen = [[0] * W for _ in range(H)]
seen[sh][sw] = True
min_step = step(sh, sw)
while que:
	(sh, sw, k) = que.popleft()
	for (hh, ww) in zip(dh, dw):
		h = sh + hh
		w = sw + ww
		if not ok(h, w) or A[h][w] == '#' or seen[h][w]:
			continue
		if k > 0:
			min_step = min(min_step, step(h, w))
			seen[h][w] = True
			que.append((h, w, k - 1))
print(min_step + 1)


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] == '#':
			continue
		if visited[ny][nx]:
			continue
		q.append((d + 1, nx, ny))
		visited[ny][nx] = 1
ans = -(-mindist // K) + 1
print(ans)


from collections import deque
(H, W, K) = map(int, input().split())
S = []
for _ in range(H):
	S.append(list(input()))
D = [[1 for i in range(W)] for j in range(H)]
for x in range(H):
	for y in range(W):
		if S[x][y] == 'S':
			sx = x
			sy = y
D[sx][sy] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ans = float('inf')
q = deque([[sx, sy, 0]])
while len(q) != 0:
	(x, y, cnt) = q.popleft()
	if cnt > K:
		break
	tmp = min(x, y, H - x - 1, W - y - 1)
	if tmp != 0:
		tmp = (tmp - 1) // K
		tmp += 2
	else:
		tmp = 1
	ans = min(ans, tmp)
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		if 0 <= nx < H and 0 <= ny < W and (S[nx][ny] != '#') and D[nx][ny]:
			D[nx][ny] = 0
			q.append([nx, ny, cnt + 1])
print(ans)


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


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
			elif d + 1 < reachable[y + dy][x + dx]:
				reachable[y + dy][x + dx] = d + 1
				q.append((y + dy, x + dx, d + 1))
	ans = 1 - -outer // K
	print(ans)
	return

def main():

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


from collections import *
(H, W, K) = map(int, input().split())
A = [list(input()) for i in range(H)]
(SX, SY) = (0, 0)
for i in range(H):
	for j in range(W):
		if A[i][j] == 'S':
			(SX, SY) = (j, i)
D = deque()
Z = set()
P = 1

def qao(y, x):
	if min(x, y) == 0 or x + 1 == W or y + 1 == H:
		print(P)
		exit()
	if (y, x) in Z:
		return False
	D.append((y, x))
	Z.add((y, x))
	return True
w4x = (1, 0, -1, 0)
w4y = (0, 1, 0, -1)

def bfs(F):
	v = 0
	for i in range(len(D)):
		v = D.popleft()
		for j in range(4):
			if A[v[0] + w4y[j]][v[1] + w4x[j]] == '.' or F:
				qao(v[0] + w4y[j], v[1] + w4x[j])
qao(SY, SX)
for i in range(K):
	bfs(0)
D = deque(Z)
while True:
	P += 1
	for i in range(K):
		bfs(1)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
(h, w, k) = map(int, input().split())
board = [list(input()) for i in range(h)]
for i in range(h):
	for j in range(w):
		if board[i][j] == 'S':
			(sx, sy) = (i, j)
from collections import deque
dxdy = [(0, 1), (1, 0), (0, -1), (-1, 0)]

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


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


import collections

def solve():

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


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)


import queue

class gridMan:

	def __init__(s, L):
		s.L = L
		s.H = len(s.L)
		s.W = len(s.L[0])

	def makeWall(s, x=-2):
		w = len(s.L[0]) + 2
		s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]

	def dist(s, S):
		T = [[-1] * s.W for _ in range(s.H)]
		q = queue.Queue()
		q.put([S[0], S[1]])
		T[S[0]][S[1]] = 0
		k = 0
		while not q.empty():
			(h, w) = q.get()
			k = T[h][w]
			for (i, j) in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
				hh = h + i
				ww = w + j
				if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
					q.put([hh, ww])
					T[hh][ww] = k + 1
		return (T, k)
(H, W, K) = list(map(int, input().split()))
A = [list(input()) for _ in range(H)]
b = '#'
r = '.'
for i in range(H):
	for j in range(W):
		if A[i][j] == b:
			A[i][j] = -1
		elif A[i][j] == r:
			A[i][j] = 0
		else:
			A[i][j] = 0
			S = [i, j]
if S[0] == 0 or S[0] == H - 1:
	print(0)
	exit()
if S[1] == 0 or S[1] == W - 1:
	print(0)
	exit()
g = gridMan(A)
g.makeWall()
(L, r) = g.dist(S)
ans = 10 ** 10
for i in range(H):
	for j in range(W):
		if 0 <= L[i][j] and L[i][j] <= K:
			t = min(i, j, H - i - 1, W - j - 1)
			if t == 0:
				print(1)
				exit()
			t = (t + K - 1) // K
			ans = min(ans, t)
print(ans + 1)


import sys
from collections import deque
input = sys.stdin.readline
inf = 10 ** 8
DX = (-1, 0, 1, 0, -1, -1, 1, 1)
DY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DX[:4]
DY = DY[:4]
(H, W, K) = map(int, input().split())
grid = [input().rstrip() for _ in range(H)]
dist = [[inf] * W for _ in range(H)]
node = deque()
for i in range(H):
	for j in range(W):
		if grid[i][j] == 'S':
			node.append((i, j))
			dist[i][j] = 0
memo = []
while node:
	(x, y) = node.popleft()
	memo.append((x, y))
	d = dist[x][y]
	if d >= K:
		continue
	for (dx, dy) in zip(DX, DY):
		nx = x + dx
		ny = y + dy
		if nx < 0 or ny < 0 or nx >= H or (ny >= W):
			continue
		if grid[nx][ny] == '#':
			continue
		if dist[nx][ny] > d + 1:
			dist[nx][ny] = d + 1
			node.append((nx, ny))
ans = inf
for (x, y) in memo:
	d = min(x, y, H - x - 1, W - y - 1)
	ans = min(ans, 1 + (d + K - 1) // K)
print(ans)


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


from collections import deque
(H, W, K) = map(int, input().split())
A = ['' for i in range(H)]
for i in range(H):
	A[i] = input()
for i in range(H):
	for j in range(W):
		if A[i][j] == 'S':
			s = (i, j)
move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
start = set([s])
que = deque([(0, s[0], s[1])])
while que:
	(count, posx, posy) = que.popleft()
	if count == K:
		continue
	for (i, j) in move:
		nx = posx + i
		ny = posy + j
		if H - 1 >= nx >= 0 and W - 1 >= ny >= 0 and (A[nx][ny] != '#') and ((nx, ny) not in start):
			start.add((nx, ny))
			que.append((count + 1, nx, ny))
ans = float('inf')
for (x, y) in start:
	test = 1 + min((abs(x - 0) - 1) // K + 1, (abs(H - 1 - x) - 1) // K + 1, (abs(y - 0) - 1) // K + 1, (abs(W - 1 - y) - 1) // K + 1)
	ans = min(ans, test)
if s[0] == 0 or s[0] == H - 1 or s[1] == 0 or (s[1] == W - 1):
	ans = 0
print(ans)


(H, W, K) = map(int, input().split())
items = []
start = []
diff = float('inf')
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
	items.append(list(input()))
	for j in range(W):
		s = items[i][j]
		if s == 'S':
			start = [i, j]
			diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
			p = [i, j]
			prev[i][j] = True
from collections import deque
que = deque([])
dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]
for i in range(4):
	x = dx[i]
	y = dy[i]
	if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
		tmp = items[start[0] + y][start[1] + x]
		if tmp == '.':
			que.append((start[0] + y, start[1] + x))
			prev[start[0] + y][start[1] + x] = True
k = K
while len(que) != 0:
	q = que.popleft()
	a = q[0]
	b = q[1]
	if abs(start[0] - a) + abs(start[1] - b) > K:
		continue
	c = min(min(a, H - 1 - a), min(b, W - 1 - b))
	if c < diff:
		diff = c
		p = (a, b)
	for i in range(4):
		x = dx[i]
		y = dy[i]
		if 0 <= a + y <= H - 1 and 0 <= b + x <= W - 1:
			if prev[a + y][b + x]:
				continue
			tmp = items[a + y][b + x]
			if tmp == '.':
				que.append((a + y, b + x))
				prev[a + y][b + x] = True
ans = 1
if diff == 0:
	print(ans)
else:
	print(ans + (K - 1 + diff) // K)


import sys
from collections import deque
readline = sys.stdin.readline
(H, W, K) = map(int, readline().split())
G = [[2] * (W + 2)]
st = (None, None)
for h in range(H):
	g = readline().strip()
	if 'S' in g:
		st = (1 + h, 1 + g.index('S'))
	G.append([2] + [1 if s == '#' else 0 for s in g] + [2])
G.append([2] * (W + 2))
DIREC = [(0, -1), (0, 1), (1, 0), (-1, 0)]
Q = deque([st])
INF = 10 ** 9 + 7
dist = [[INF] * (W + 2) for _ in range(H + 2)]
for (h, w) in Q:
	dist[h][w] = 0
Q2 = deque([st])
ans = INF
while Q:
	(nh, nw) = Q.pop()
	for (dh, dw) in DIREC:
		(fh, fw) = (nh + dh, nw + dw)
		if G[fh][fw]:
			continue
		if dist[fh][fw] > 1 + dist[nh][nw]:
			dist[fh][fw] = 1 + dist[nh][nw]
			if dist[fh][fw] <= K:
				Q2.append((fh, fw))
				if fh == 1 or fh == H or fw == 1 or (fw == W):
					ans = 1
			Q.appendleft((fh, fw))
if ans == INF:
	dist = [[INF] * (W + 2) for _ in range(H + 2)]
	for (h, w) in Q2:
		dist[h][w] = 0
	while Q2:
		(nh, nw) = Q2.pop()
		for (dh, dw) in DIREC:
			(fh, fw) = (nh + dh, nw + dw)
			if G[fh][fw] == 2:
				continue
			if dist[fh][fw] > 1 + dist[nh][nw]:
				dist[fh][fw] = 1 + dist[nh][nw]
				if fh == 1 or fh == H or fw == 1 or (fw == W):
					ans = min(ans, 2 + (dist[fh][fw] - 1) // K)
				Q2.appendleft((fh, fw))
print(ans)


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


import sys

def main():
	input = sys.stdin.readline
	(H, W, K) = map(int, input().split())
	A = [list(input()) for _ in range(H)]
	from collections import deque
	q = deque()
	for i in range(H):
		for j in range(W):
			if A[i][j] == 'S':
				q.append((i, j, 0))
				A[i][j] = '#'
	ans = 10 ** 9
	while q:
		(i, j, d) = q.popleft()
		if i == 0 or i == H - 1 or j == 0 or (j == W - 1):
			print(1)
			exit()
		ans = min(ans, (min(i, j, H - 1 - i, W - 1 - j) + K - 1) // K + 1)
		if d == K:
			continue
		for (di, dj) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
			(ni, nj) = (i + di, j + dj)
			if A[ni][nj] != '#':
				q.append((ni, nj, d + 1))
				A[ni][nj] = '#'
	print(ans)
main()


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 = 1000000000.0
while Q:
	(c, i, j) = Q.popleft()
	d = min(d, i, j, ~i + H, ~j + W)
	if c < K:
		for (h, w) in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
			if H > h > -1 < w < W and '.' == A[h][w]:
				A[h][w] = 0
				Q += ((c + 1, h, w),)
print(1 - -d // K)


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)):
	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))
m = min(M)
print((m + K - 1) // K + 1)


import math
import queue
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

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


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

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

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


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


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)


from collections import deque

def updiv(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1
(H, W, K) = map(int, input().split())
A = []
for i in range(H):
	a = list(input())
	A.append(a)
q = deque([])
for i in range(H):
	for j in range(W):
		if A[i][j] == 'S':
			q.append([i, j])
			A[i][j] = 0
while len(q) > 0:
	now = q.popleft()
	ni = now[0]
	nj = now[1]
	if A[ni][nj] < K:
		if ni - 1 >= 0 and A[ni - 1][nj] != '#':
			if A[ni - 1][nj] == '.' or A[ni][nj] + 1 < A[ni - 1][nj]:
				A[ni - 1][nj] = A[ni][nj] + 1
				q.append([ni - 1, nj])
		if ni + 1 < H and A[ni + 1][nj] != '#':
			if A[ni + 1][nj] == '.' or A[ni][nj] + 1 < A[ni + 1][nj]:
				A[ni + 1][nj] = A[ni][nj] + 1
				q.append([ni + 1, nj])
		if nj - 1 >= 0 and A[ni][nj - 1] != '#':
			if A[ni][nj - 1] == '.' or A[ni][nj] + 1 < A[ni][nj - 1]:
				A[ni][nj - 1] = A[ni][nj] + 1
				q.append([ni, nj - 1])
		if nj + 1 < W and A[ni][nj + 1] != '#':
			if A[ni][nj + 1] == '.' or A[ni][nj] + 1 < A[ni][nj + 1]:
				A[ni][nj + 1] = A[ni][nj] + 1
				q.append([ni, nj + 1])
ans = float('inf')
for i in range(H):
	for j in range(W):
		if A[i][j] not in ['.', '#']:
			ans = min(ans, 1 + updiv(i, K), 1 + updiv(j, K), 1 + updiv(H - i - 1, K), 1 + updiv(W - j - 1, K))
print(ans)


def main(h, w, k, a):
	s = (-1, -1)
	for i in range(h):
		for j in range(w):
			if a[i][j] == 'S':
				s = (i, j)
				break
		if s[0] != -1:
			break
	inf = float('inf')
	da = [[inf] * w for _ in range(h)]
	da[s[0]][s[1]] = 0
	todo = [s]
	dst = min(s[0], h - s[0] - 1, s[1], w - s[1] - 1)
	cnt = 0
	while cnt < k and todo:
		ntodo = []
		while todo:
			(i, j) = todo.pop()
			for (di, dj) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
				if 0 <= i + di < h and 0 <= j + dj < w and (a[i + di][j + dj] == '.') and (da[i + di][j + dj] > da[i][j] + 1):
					da[i + di][j + dj] = da[i][j] + 1
					ntodo.append((i + di, j + dj))
					dst = min(dst, i + di, h - i - di - 1, j + dj, w - j - dj - 1)
		cnt += 1
		todo = ntodo
	return 1 + (dst + k - 1) // k
(h, w, k) = map(int, input().split())
a = [input() for _ in range(h)]
print(main(h, w, k, a))


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


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)


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)


(h, w, k) = map(int, input().split())
a = [list(input()) for i in range(h)]
b = [[1] * w for i in range(h)]
c = 0
for i in range(h):
	if c:
		break
	for j in range(w):
		if a[i][j] == 'S':
			c = 1
			p = [i, j]
			b[i][j] = 0

def f(x, y):
	return min(x, w - y - 1, y, h - x - 1)
an = f(p[0], p[1])
q = [p]
c = 0
while q and c != k:
	c += 1
	d = []
	x = [0, 0, 1, -1]
	y = [1, -1, 0, 0]
	for (i, j) in q:
		for (s, t) in zip(x, y):
			if 0 < i + s < h - 1 and 0 < j + t < w - 1:
				if b[i + s][j + t]:
					if a[i + s][j + t] == '.':
						an = min(an, f(i + s, j + t))
						b[i + s][j + t] = 0
						d.append([i + s, j + t])
			elif a[i + s][j + t] == '.':
				print(1)
				exit()
	q = d[:]
print(2 + (an - 1) // k)


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