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):
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=='

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

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

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

Solution (Python):
import sys
from collections import deque

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

inf = 1<<60

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

    si = -1
    sj = -1

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

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

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

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

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

    ans = inf

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

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

        if ans == 0:
            print(1)
            return

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

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

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

    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque

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

inf = 1<<60

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

    si = -1
    sj = -1

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

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

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

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

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

    ans = inf

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

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

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

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

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

    print(ans)

if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque

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

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

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

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

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

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

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

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

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

Solution (Python):
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] != '
                pos.append((r, c))
                dic[(r, c)] = m
    i += 1

print(ans)

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

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

Solution (Python):
from collections import deque
h, w, k = map(int, raw_input().split())
A = [raw_input() for i in xrange(h)]
sx = sy = 0
for i in xrange(h):
    idx = A[i].find('S')
    if idx != -1:
        sx = idx; sy = i
        break

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

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

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