Problem:


Score : 700 points

Problem Statement

Takahashi is locked within a building.

This building consists of H×W rooms, arranged in H rows and W columns.
We will denote the room at the i-th row and j-th column as (i,j). The state of this room is represented by a character A_{i,j}. If A_{i,j}= #, the room is locked and cannot be entered; if A_{i,j}= ., the room is not locked and can be freely entered.
Takahashi is currently at the room where A_{i,j}= S, which can also be freely entered.

Each room in the 1-st row, 1-st column, H-th row or W-th column, has an exit.
Each of the other rooms (i,j) is connected to four rooms: (i-1,j), (i+1,j), (i,j-1) and (i,j+1).

Takahashi will use his magic to get out of the building. In one cast, he can do the following:

Move to an adjacent room at most K times, possibly zero. Here, locked rooms cannot be entered.

Then, select and unlock at most K locked rooms, possibly zero. Those rooms will remain unlocked from then on.

His objective is to reach a room with an exit. Find the minimum necessary number of casts to do so.

It is guaranteed that Takahashi is initially at a room without an exit.

Constraints

3 ≤ H ≤ 800

3 ≤ W ≤ 800

1 ≤ K ≤ H×W

Each A_{i,j} is # , .  or S.

There uniquely exists (i,j) such that A_{i,j}= S, and it satisfies 2 ≤ i ≤ H-1 and 2 ≤ j ≤ W-1.

Input

Input is given from Standard Input in the following format:

H W K
A_{1,1}A_{1,2}...A_{1,W}
:
A_{H,1}A_{H,2}...A_{H,W}

Output

Print the minimum necessary number of casts.

Sample Input 1

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

Sample Output 1

1

Takahashi can move to room (1,2) in one cast.

Sample Input 2

3 3 3
###
#S#
###

Sample Output 2

2

Takahashi cannot move in the first cast, but can unlock room (1,2).
Then, he can move to room (1,2) in the next cast, achieving the objective in two casts.

Sample Input 3

7 7 2
#######
#######
##...##
###S###
##.#.##
###.###
#######

Sample Output 3

2



Sample input:
3 3 3
#.#
#S.
###


Sample output:
1

Submission status: Time Limit Exceeded

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

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

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

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

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

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

print(1+ceil(min_dis/k))

Submission status: Time Limit Exceeded

Solution code:
if __name__=='__main__':
    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))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from math import ceil
H,W,K=map(int,input().split())
grid=[input() for i in range(H)]
G={}
                               
for i in range(H):
  for j in range(W):
    if grid[i][j]=="S":
      S=(i,j)
    if grid[i][j]!="#":
      G[(i,j)]=set()
      if i>0:
        if grid[i-1][j]!="#":
          G[(i,j)].add((i-1,j))
      if i<H-1:
        if grid[i+1][j]!="#":
          G[(i,j)].add((i+1,j))
      if j>0:
        if grid[i][j-1]!="#":
          G[(i,j)].add((i,j-1))
      if j<W-1:
        if grid[i][j+1]!="#":
          G[(i,j)].add((i,j+1))
stack=deque([(S[0],S[1],0)])
visited=[[False]*(W) for i in range(H)]
visited[S[0]][S[1]]=True
a=float("inf")
while stack:
  y,x,m=stack.popleft()
  if m>K:
    break
  a=min(a,min(x,W-1-x,y,H-1-y))
  for k in G[(y,x)]:
    if not visited[k[0]][k[1]]:
      stack.append((k[0],k[1],m+1))
      visited[k[0]][k[1]]=True
ans=1+ceil(a/K)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
from math import ceil
H,W,K=map(int,input().split())
grid=[input() for i in range(H)]
G=defaultdict(set)
                               
for i in range(H):
  for j in range(W):
    if grid[i][j]=="S":
      S=(i,j)
    if grid[i][j]!="#":
      if i>0:
        if grid[i-1][j]!="#":
          G[(i,j)].add((i-1,j))
      if i<H-1:
        if grid[i+1][j]!="#":
          G[(i,j)].add((i+1,j))
      if j>0:
        if grid[i][j-1]!="#":
          G[(i,j)].add((i,j-1))
      if j<W-1:
        if grid[i][j+1]!="#":
          G[(i,j)].add((i,j+1))

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

Submission status: Time Limit Exceeded

Solution code:
# https://beta.atcoder.jp/contests/agc014/submissions/1268295
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)]
    visited = [[False for _ in range(W)] for _ in range(H)]

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

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

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        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:
                q.append((nr, nc, k + 1))

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# https://beta.atcoder.jp/contests/agc014/submissions/1268295
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)]
    visited = [[False for _ in range(W)] for _ in range(H)]

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

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

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        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:
                q.append((nr, nc, k + 1))
                n += 1
        i += 1

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


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

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

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

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

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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

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

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

        if t == 0:
            print(1)
            return

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

from collections import deque

INF = float('inf')


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

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

    q = deque()
    q.append((sy, sx, 0))
    t = INF
    n = 1
    while n > 0:
        r, c, k = q.popleft()
        n -= 1
        visited[r][c] = True
        t = min(t, r, H - 1 - r, c, W - 1 - c)

        if t == 0:
            print(1)
            return

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

from collections import deque

INF = float('inf')


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

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

    q = deque()
    q.append((sy, sx, 0))
    t = INF
    while len(q) > 0:
        r, c, k = q.popleft()
        visited[r][c] = True
        t = min(t, r, H - 1 - r, c, W - 1 - c)

        if t == 0:
            print(1)
            return

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from collections import deque


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


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


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

q = deque()
q.append((sy, sx, 0))
while len(q) > 0:
    y, x, k = q.popleft()
    b[y][x] = True
    sl = shortest_len(y, x)
    need_len = min(need_len, sl)
    if sl - (K - k) >= need_len: continue
    if k == K: continue
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        ny, nx = y + dy, x + dx
        if not(0 <= ny < H and 0 <= nx < W): continue
        if a[ny][nx] == '#': continue
        if b[ny][nx]: continue
        q.append((y + dy, x + dx, k + 1))

print(1 + ceil(need_len / K))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from collections import deque


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


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


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

q = deque()
q.append((sy, sx, 0))
while len(q) > 0:
    y, x, k = q.popleft()
    if not (0 <= y < H and 0 <= x < W): continue
    if a[y][x] == '#': continue
    if b[y][x]: continue
    b[y][x] = True
    sl = shortest_len(y, x)
    need_len = min(need_len, sl)
    if sl - (K - k) >= need_len: continue
    if k == K: continue
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        q.append((y + dy, x + dx, k + 1))

print(1 + ceil(need_len / K))

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
from collections import deque


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


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


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

q = deque()
q.append((sy, sx, 0))
while len(q) > 0:
    y, x, k = q.popleft()
    if not (0 <= y < H and 0 <= x < W): continue
    if a[y][x] == '#': continue
    if b[y][x]: continue
    b[y][x] = True
    need_len = min(need_len, shortest_len(y, x))
    if k == K: continue
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        q.append((y + dy, x + dx, k + 1))

print(1 + ceil(need_len / K))

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

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

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

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


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

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


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

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

        return d

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

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

print(main())

Submission status: Time Limit Exceeded

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

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

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


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

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


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

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

        return d

    d = search([tuple(st)],True,k)
    r = inf
    for g,v in d.items():
        if 0 < g[0] < h-1 and 0 < g[1] < w-1:
            tr = 1 + (min(g[0],g[1],h-g[0]-1,w-g[1]-1) + k - 1) // k
            if r > tr:
                r = tr
            continue
        return 1
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
H, W, K = map(int, input().split())
 
A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')
 
def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

visited = [tuple(S)]
l = 0
for _ in range(K):
    r = len(visited)
    for p in range(l, r):
        x, y = visited[p]
        if is_edge(x, y):
            continue
        if A[x - 1][y] == '.':
            if (x - 1, y) not in visited:
                visited.append((x - 1, y))
        if A[x + 1][y] == '.':
            if (x + 1, y) not in visited:
                visited.append((x + 1, y))
        if A[x][y - 1] == '.':
            if (x , y - 1) not in visited:
                visited.append((x, y - 1))
        if A[x][y + 1] == '.':
            if (x , y + 1) not in visited:
                visited.append((x, y + 1))
    l = r

 
def get_dist(x, y):
    return min(x, y, H - x - 1, W - y - 1)
 
min_dist = get_dist(S[0], S[1])
for p in visited:
    min_dist = min(min_dist, get_dist(*p))
 
print(ceil(min_dist / K) + 1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
H, W, K = map(int, input().split())
 
A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')
 
def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

visited = [(S[0], S[1])]
l = 0
for i in range(K):
    r = len(visited)
    for p in range(l, r):
        x, y = visited[p]
        if is_edge(x, y):
            break
        if A[x - 1][y] == '.':
            if (x - 1, y) not in visited:
                visited.append((x - 1, y))
        if A[x + 1][y] == '.':
            if (x + 1, y) not in visited:
                visited.append((x + 1, y))
        if A[x][y - 1] == '.':
            if (x , y - 1) not in visited:
                visited.append((x, y - 1))
        if A[x][y + 1] == '.':
            if (x , y + 1) not in visited:
                visited.append((x, y + 1))
    l = r

 
def get_dist(x, y):
    return min(x, y, H - x - 1, W - y - 1)
 
min_dist = get_dist(S[0], S[1])
for p in visited:
    min_dist = min(min_dist, get_dist(p[0], p[1]))
 
print(ceil(min_dist / K) + 1)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
H, W, K = map(int, input().split())
 
A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')
 
def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

visited = [(S[0], S[1])]
l = 0
for i in range(K):
    r = len(visited)
    for p in range(l, r):
        x, y = visited[p]
        if is_edge(x, y):
            break
        if A[x - 1][y] == '.':
            visited.append((x - 1, y))
        if A[x + 1][y] == '.':
            visited.append((x + 1, y))
        if A[x][y - 1] == '.':
            visited.append((x, y - 1))
        if A[x][y + 1] == '.':
            visited.append((x, y + 1))
    l = r

 
def get_dist(x, y):
    return min(x, y, H - x - 1, W - y - 1)
 
min_dist = get_dist(S[0], S[1])
for p in visited:
    min_dist = min(min_dist, get_dist(p[0], p[1]))
 
print(ceil(min_dist / K) + 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, K = map(int, input().split())
ar = []
for _ in range(H):
    ar.append([c for c in input()])
ar = np.array(ar)
sh, sw = np.where(ar == 'S')
sh=sh[0]
sw=sw[0]
flag = 1
count = 0
ard = np.array([H*W]*W*H).reshape(H,W)
ar[sh,sw] = 0
ard[sh, sw] = min(sh, H-1 - sh, sw, W-1 - sw) 
check = np.array([[sh, sw]])
ans = 1
while flag and count < K:
    flag = 0
    count += 1
    s = np.array([[1,0],[0,1],[-1,0],[0,-1]])
    add_check = []
    for d in s:
        cos = check + d
        np.delete(check, 0)
        for co in cos:
            if co[0] >= 0 and co[0] <= H-1 and co[1] >= 0 and co[1] <= W-1:
                if ar[co[0],co[1]] == '.':
##                    if co[0]==0 or co[0]==H-1 or co[1]==0 or co[1]==W-1:
##                        ans = 0
                    ar[co[0],co[1]] = count
    ##                ar[co[0],co[1]] = min(co[0] - 0, H-1 - co[0], co[1] - 0, W-1 - co[1])
                    ard[co[0],co[1]] = min(co[0] - 0, H-1 - co[0], co[1] - 0, W-1 - co[1])
                    flag = 1

                    add_check.append(co)

                    np.append(check, [co],axis = 0)

    check = np.array(add_check)

dist = np.min(ard)

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

Submission status: Time Limit Exceeded

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

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

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


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

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


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

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

        return d

    d = search([tuple(st)],True,k)
    for g,v in d.items():
        if 0 < g[0] < h-1 and 0 < g[1] < w-1:
            continue
        return 1
    ss = []
    for g in d.keys():
        ss.append(g)
    d = search(ss,False,k)
    r = inf
    for g,v in d.items():
        if 0 < g[0] < h-1 and 0 < g[1] < w-1:
            continue
        t = (v+k-1) // k
        if t < r:
            r = t
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int, raw_input().split())
a = []
visited = {}
ans = float('inf')
for _ in range(h):
  row = list(raw_input())
  a.append(row)


s = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == 'S':
      s = (i,j)

# def visit(i,j,ki):
q = [(s[0], s[1], k)]
while len(q) > 0:
  i,j,ki = q.pop(0)

  visited[(i,j)] = True
  d = min(h-1-i, i, w-1-j, j)
  ans = min(ans, (d+k-1) / k)

  if ki == 0:
    continue
  # if i < 0 or h <= i:
  #   continue
  # if j < 0 or w <= j:
  #   continue
  # if a[i][j] == '#':
  #   continue
  # if (i,j) in visited:
  #   continue

  if 0 <= j < w:
    if 0 <= i+1 < h and a[i+1][j] != '#' and (i+1,j) not in visited:
      q.append((i+1, j, ki-1))
    if 0 <= i-1 < h and a[i-1][j] != '#' and (i-1,j) not in visited:
      q.append((i-1, j, ki-1))

  if 0 <= i < h:
    if 0 <= j+1 < w and a[i][j+1] != '#' and (i,j+1) not in visited:
      q.append((i, j+1, ki-1))
    if 0 <= j-1 < w and a[i][j-1] != '#' and (i,j-1) not in visited:
      q.append((i, j-1, ki-1))

  # visited[(i,j)] = True
  # d = min(h-1-i, i, w-1-j, j)
  # dk = (d+k-1) / k
  # ans.append(dk)

  # q.append((i+1, j, ki-1))
  # q.append((i-1, j, ki-1))
  # q.append((i, j+1, ki-1))
  # q.append((i, j-1, ki-1))

# visit(s[0], s[1], k)
# print visited
print ans+1