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

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

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


ans = INF

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

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

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

    distance = dist[i][j] + 1

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W, K = map(int, input().split())
A = ['' for _ in range(H)]
B = [[[H * W, 0, 0] for _ in range(W)] for _ in range(H)]
Q = []
for i in range(H):
  A[i] = input()
  j = A[i].find('S')
  if j >= 0:
    B[i][j] = [1, 0, 0]
    heapq.heappush(Q, [1, 0, 0, i, j])
def drill(x, y, a, b):
  _B = list(B[x][y])
  if A[a][b] == '.':
    _B[1] += 1
  else:
    _B[2] += 1
    if _B[0] <= -(-_B[2] // K):
      _B[0] = -(-_B[2] // K) + 1
      _B[1] = 1
    else:
      _B[1] += 1
  if _B[1] > K:
    _B[1] -= K
    _B[0] += 1
  if _B < B[a][b]:
    B[a][b] = _B
    heapq.heappush(Q, _B + [a, b])
while Q:
  q = heapq.heappop(Q)
  x = q[3]
  y = q[4]
  if x == 0 or x == W - 1 or y == 0 or y == H - 1:
    print(q[0])
    break
  drill(x, y, x - 1, y)
  drill(x, y, x, y - 1)
  drill(x, y, x + 1, y)
  drill(x, y, x, y + 1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W, K = map(int, input().split())
A = ['' for _ in range(H)]
B = [[[H * W, 0, 0] for _ in range(W)] for _ in range(H)]
Q = []
for i in range(H):
  A[i] = input()
  for j in range(W):
    if A[i][j] == 'S':
      B[i][j] = [1, 0, 0]
      heapq.heappush(Q, [1, 0, 0, i, j])
def drill(x, y, a, b):
  if A[a][b] == '.':
    _B = list(B[x][y])
    _B[1] += 1
  else:
    _B = list(B[x][y])
    _B[2] += 1
    if _B[0] <= -(-_B[2] // K):
      _B[0] = -(-_B[2] // K) + 1
      _B[1] = 1
    else:
      _B[1] += 1
  if _B[1] > K:
    _B[1] -= K
    _B[0] += 1
  if _B < B[a][b]:
    B[a][b] = _B
    heapq.heappush(Q, _B + [a, b])
while Q:
  d, w, b, x, y = heapq.heappop(Q)
  if x == 0 or x == W - 1 or y == 0 or y == H - 1:
    print(d)
    break
  drill(x, y, x - 1, y)
  drill(x, y, x, y - 1)
  drill(x, y, x + 1, y)
  drill(x, y, x, y + 1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import os
import sys
from collections import deque

import numpy as np

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 = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='S1')

[sh], [sw] = np.where(A == b'S')
A = (A == b'.').tolist()


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

Submission status: Time Limit Exceeded

Solution code:
import math
import math
import os
import sys
from collections import deque

import numpy as np

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 = np.array([list(sys.stdin.readline().rstrip()) for _ in range(H)], dtype='S1')

[sh], [sw] = np.where(A == b'S')
A = A == b'.'


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 = np.zeros((H, W), dtype=bool)
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 not 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)

Submission status: Time Limit Exceeded

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

    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)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w,K = map(int,input().split())

maze = [[x for x in input()] for _ in range(h)]

sx = 0
sy = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == 'S':
            sx = j
            sy = i

d = [[float('inf')]*w for _ in range(h)]
d[sy][sx] = 0

q = deque([[sy,sx]])
c = 0

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,BFS(i,j))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w,K = map(int,input().split())

maze = [[x for x in input()] for _ in range(h)]

sx = 0
sy = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == 'S':
            sx = j
            sy = i

d = [[float('inf')]*w for _ in range(h)]
d[sy][sx] = 0

q = deque([[sy,sx]])
c = 0

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
                q.append([ny,nx])
                c += 1
    if c >= 4*K**2:
        break
    

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,BFS(i,j))

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

Submission status: Time Limit Exceeded

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

#print(A)
#print(S)
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])
#print(ans)
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(B)
#print(ans)
print(math.ceil(ans/K)+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

    prev[a][b] = True
    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))
    k -= 1

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)

Submission status: Time Limit Exceeded

Solution code:
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))
k = K
while len(que) != 0 and k != 0:
    que2 = deque([])
    while len(que) != 0:
        q = que.popleft()
        a = q[0]
        b = q[1]
        prev[a][b] = True
        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 == ".":
                    que2.append((a + y, b + x))
    k -= 1
    que = que2

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)

Submission status: Time Limit Exceeded

Solution code:
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))
k = K
while len(que) != 0 and k != 0:
    que2 = deque([])
    while len(que) != 0:
        q = que.popleft()
        prev[q[0]][q[1]] = True
        if min(diff, min(q[0], H - 1 - q[0], min(q[1], W - 1 - q[1]))) < diff:
            diff = min(diff, min(q[0], H - 1 - q[0], min(q[1], W - 1 - q[1])))
            p = (q[0], q[1])

        for i in range(4):
            x = dx[i]
            y = dy[i]
            if 0 <= q[0] + y <= H - 1 and 0 <= q[1] + x <= W - 1:
                if prev[q[0] + y][q[1] + x]:
                    continue
                tmp = items[q[0] + y][q[1] + x]
                if tmp == ".":
                    que2.append((q[0] + y, q[1] + x))
    k -= 1
    que = que2

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input=sys.stdin.readline
H,W,K=map(int,input().split())

s=[0,0]
A=[]
for i in range(H):
    a=list(input())
    for j in range(W):
        if a[j]=="S":
            s=[i,j]
    A.append(a)
#print(A)
#print(s)
B=[[10**6 for j in range(W)]for i in range(H)]
#print(B)
B[s[0]][s[1]]=0
Q=[]
for i in range(4):
    if s[0]+1>=H:
        print(1)
        exit()
    elif A[s[0]+1][s[1]]==".":
        Q.append([1,s[0]+1,s[1]])
    if s[0]-1<0:
        print(1)
        exit()
    elif A[s[0]-1][s[1]]==".":
        Q.append([1,s[0]-1,s[1]])
    if s[1]+1>=W:
        print(1)
        exit()
    elif A[s[0]][s[1]+1]==".":
        Q.append([1,s[0],s[1]+1])
    if s[1]-1<0:
        print(1)
        exit()
    elif A[s[0]][s[1]-1]==".":
        Q.append([1,s[0],s[1]-1])
        
heapq.heapify(Q)
for i in range(10**6):
    if len(Q)==0:
        break
    else:
        if B[Q[0][1]][Q[0][2]]==10**6:
            B[Q[0][1]][Q[0][2]]=Q[0][0]
            q=Q[0]
            heapq.heappop(Q)
            for j in range(4):
                if q[1]+1<=H-1 and K>=q[0]:
                    if A[q[1]+1][q[2]]==".":
                        heapq.heappush(Q,[q[0]+1,q[1]+1,q[2]])
                if q[1]-1>=0 and K>=q[0]:
                    if A[q[1]-1][q[2]]==".":
                        heapq.heappush(Q,[q[0]+1,q[1]-1,q[2]])
                if q[2]+1<=W-1 and K>=q[0]:
                    if A[q[1]][q[2]+1]==".":
                        heapq.heappush(Q,[q[0]+1,q[1],q[2]+1])
                if q[2]-1>=0 and K>=q[0]:
                    if A[q[1]][q[2]-1]==".":
                        heapq.heappush(Q,[q[0]+1,q[1],q[2]-1])
    heapq.heappop(Q)
#print(A)
#print(B)

import math

MIN=10**6
for i in range(H):
    for j in range(W):
        if B[i][j]<=K:
            U=math.ceil(i/K)
            L=math.ceil(j/K)
            D=math.ceil((H-1-i)/K)
            R=math.ceil((W-1-j)/K)
            if min(U,L,D,R)+1<MIN:
                MIN=min(U,L,D,R)+1
print(MIN)

Submission status: Time Limit Exceeded

Solution code:
dxys = [(-1,0), (1,0), (0,-1), (0,1)]

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

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) for _ in range(H)]
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 (0 <= x2 <= H-1 and 0 <= y2 <= W-1): continue
            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][y]:
            dist = min(x, H-1-x, y, W-1-y)
            ans = min(ans, -(-dist//K)+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from math import ceil

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

# 2回目以降の移動において、すべての部屋は開いていると考えてよい
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)

Submission status: Time Limit Exceeded

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

def minCost(x,y):
    return min(start[X], W-1-start[X], start[Y], H-1-start[Y]) // K
search = []
searched = [[K+1 for w in range(W)] for h in range(H)]
search.append((start[X],start[Y], 0))
vector = [(1,0),(-1,0),(0,1),(0,-1)]
max_x,min_x,max_y,min_y = 0,W-1,0,H-1
while len(search) > 0:
    x,y,cnt = search.pop()
    if x == 0 or x == W-1 or y == 0 or y == H-1:
        print(1)
        exit()
    if cnt >= searched[y][x]:
        continue
    searched[y][x] = cnt
    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 cnt+1 >= searched[newY][newX] and cnt < K and A[newY][newX] != "#":
            search.append((newX,newY,cnt+1))
dist = min(min_x, min_y, W-1-max_x, H-1-max_y)
print(1 + (dist+K-1)//K)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
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':
        break
visited = [[False] * W for _ in range(H)]
ans = min([i, H - 1 - i, j, W - 1 - j])
Q = collections.deque([[i, j, K]])
while Q:
    h, w, res = Q.popleft()
    visited[h][w] = True
    ans = min([ans, h, H - 1 - h, w, W - 1 - w])
    if res:
        res -= 1
        if h and A[h - 1][w] == '.':
            Q += [[h - 1, w, res]]
        if h < H - 1 and A[h + 1][w] == '.':
            Q += [[h + 1, w, res]]
        if w and A[h][w - 1] == '.':
            Q += [[h, w - 1, res]]
        if w < W - 1 and A[h][w + 1] == '.':
            Q += [[h, w + 1, res]]
print(1 + math.ceil(ans / K))

Submission status: Time Limit Exceeded

Solution code:
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
ans = min([i, H - 1 - i, j, W - 1 - j])
Q = collections.deque([[i, j, K, ans]])
while Q:
    h, w, res, dist = Q.popleft()
    A[h][w] = '#'
    ans = min([ans, h, H - 1 - h, w, W - 1 - w])
    if ans == 0:
        print(1)
        exit()
    if res:
        res -= 1
        if h and A[h - 1][w] == '.':
            Q += [[h - 1, w, res, ans]]
        if h < H - 1 and A[h + 1][w] == '.':
            Q += [[h + 1, w, res, ans]]
        if w and A[h][w - 1] == '.':
            Q += [[h, w - 1, res, ans]]
        if w < W - 1 and A[h][w + 1] == '.':
            Q += [[h, w + 1, res, ans]]
print(1 + math.ceil(ans / K))

Submission status: Time Limit Exceeded

Solution code:
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, K]])
hmin = hmax = i
wmin = wmax = j
while Q:
    h, w, res = Q.popleft()
    A[h][w] = '#'
    hmin = min(hmin, h)
    hmax = max(hmax, h)
    wmin = min(wmin, w)
    wmax = max(wmax, w)
    if res:
        res -= 1
        if h and A[h - 1][w] == '.':
            Q += [[h - 1, w, res]]
        if h < H - 1 and A[h + 1][w] == '.':
            Q += [[h + 1, w, res]]
        if w and A[h][w - 1] == '.':
            Q += [[h, w - 1, res]]
        if w < W - 1 and A[h][w + 1] == '.':
            Q += [[h, w + 1, res]]
print(1 +
      min([math.ceil(_ / K)
           for _ in (hmin, H - 1 - hmax, wmin, W - 1 - wmax)]))

Submission status: Time Limit Exceeded

Solution code:
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]])
hmin = hmax = i
wmin = wmax = j
while Q:
    h, w, dist = Q.popleft()
    A[h][w] = '#'
    hmin = min(hmin, h)
    hmax = max(hmax, h)
    wmin = min(wmin, w)
    wmax = max(wmax, w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                Q += [[nh, nw, dist + 1]]
print(1 +
      min([math.ceil(_ / K)
           for _ in (hmin, H - 1 - hmax, wmin, W - 1 - wmax)]))

Submission status: Time Limit Exceeded

Solution code:
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]])
aH = []
aW = []
while Q:
    h, w, dist = Q.popleft()
    A[h][w] = '#'
    aH += [h]
    aW += [w]
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(aH), H - 1 - max(aH), min(aW), W - 1 - max(aW))
]))

Submission status: Time Limit Exceeded

Solution code:
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()
    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 and A[nh][nw] == '.':
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))

Submission status: Time Limit Exceeded

Solution code:
import itertools, math, collections
H, W, K = [int(_) for _ in input().split()]
A = [[2 if _ == 'S' else 1 if _ == '.' else 0 for _ in input()]
     for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 2:
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    A[h][w] = 0
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw]:
                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))
]))