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: Wrong Answer

Solution code:
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))//k), -((-j)//k), -((-(w-j))//k))

print(ans+1)

Submission status: Wrong Answer

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

    in_black = [[-1]*W for _ in range(H)]
    b = []

    goal = False
    ans = 0
    while not goal:
        ans += 1
        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] == "#":
                        if in_black[nh][nw] == -1:
                            in_black[nh][nw] = 0
                            b.append((nh, nw))
                        elif in_black[nh][nw] == 1 and not checked[nh][nw]:
                            checked[nh][nw] = True
                            qq.append((nh, nw))
                    elif not checked[nh][nw]:
                        checked[nh][nw] = True
                        qq.append((nh, nw))
            q = qq
        
        if goal: break
        
        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 in_black[nh][nw] == -1:
                    in_black[nh][nw] = 0
                    b.append((nh, nw))
        
        if goal: break
        
        for i in range(K):
            bb = []
            for h, w in b:
                in_black[h][w] = 1
                if i == 0:
                    checked[h][w] = True
                    q.append((h, w))
                nexts = []
                if h != 0: nexts.append((h-1, w))
                if h != H-1: nexts.append((h+1, w))
                if w != 0: nexts.append((h, w-1))
                if w != W-1: nexts.append((h, w+1))
                for nh, nw in nexts:
                    if state[nh][nw] == "#" and in_black[nh][nw] == -1:
                        in_black[nh][nw] = 0
                        bb.append((nh, nw))
            b = bb

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    in_black = [[-1]*W for _ in range(H)]
    b = []

    goal = False
    ans = 0
    while not goal:
        ans += 1
        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] == "#":
                        if in_black[nh][nw] == -1:
                            in_black[nh][nw] = 0
                            b.append((nh, nw))
                        elif in_black[nh][nw] == 1 and not checked[nh][nw]:
                            checked[nh][nw] = True
                            qq.append((nh, nw))
                    elif not checked[nh][nw]:
                        checked[nh][nw] = True
                        qq.append((nh, nw))
            q = qq
        
        if goal: break

        for h, w in q:
            if h == 0 or h == H-1 or w == 0 or w == W-1:
                goal = True
                ans += 1
                break
            nexts = [(h, w-1), (h, w+1), (h-1, w), (h+1, w)]
            for nh, nw in nexts:
                if state[nh][nw] == "#" and in_black[nh][nw] == -1:
                    in_black[nh][nw] = 0
                    b.append((nh, nw))
        
        if goal: break
        
        for i in range(K):
            bb = []
            for h, w in b:
                in_black[h][w] = 1
                if i == 0:
                    checked[h][w] = True
                    q.append((h, w))
                nexts = []
                if h != 0: nexts.append((h-1, w))
                if h != H-1: nexts.append((h+1, w))
                if w != 0: nexts.append((h, w-1))
                if w != W-1: nexts.append((h, w+1))
                for nh, nw in nexts:
                    if state[nh][nw] == "#" and in_black[nh][nw] == -1:
                        in_black[nh][nw] = 0
                        bb.append((nh, nw))
            b = bb

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == 'S':
            sx = i
            sy = j
            break
dist = [[-1]*W for _ in range(H)]
dist[sx][sy] = 0
que = deque([(sx, sy)])
dire = [(1, 0), (-1, 0), (0, 1), (0, -1)]
m = min(sx, sy, H-1-sx, W-1-sy)
while que:
    x, y = que.pop()
    if m==0:
        break
    d = dist[x][y]
    if d == K:
        break
    for dx, dy in dire:
        nx = x+dx
        ny = y+dy
        if dist[nx][ny]<0 and A[nx][ny] == '.':
            dist[nx][ny] = d+1
            que.append((nx, ny))
            tmp = min(nx, ny, H-1-nx, W-1-ny)
            m = min(tmp, m)
print((m-1)//K+1+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j] == 'S':
            sx = i
            sy = j
            break
dist = [[-1]*W for _ in range(H)]
dist[sx][sy] = 0
que = deque([(sx, sy)])
dire = [(1, 0), (-1, 0), (0, 1), (0, -1)]
m = min(sx, sy, H-1-sx, W-1-sy)
while que:
    x, y = que.pop()
    if m==0:
        break
    d = dist[x][y]
    if d == K:
        break
    for dx, dy in dire:
        nx = x+dx
        ny = y+dy
        if dist[nx][ny]<0 and A[nx][ny] == '.':
            dist[nx][ny] = d+1
            que.append((nx, ny))
            tmp = min(nx, ny, H-1-nx, W-1-ny)
            m = min(tmp, m)
print(m//K+1)

Submission status: Wrong Answer

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

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()
    if cnt >= K:
        continue

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    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.append((cnt + 1, ni, nj))

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

Submission status: Wrong Answer

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

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()
    if cnt >= K:
        break

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    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.append((cnt + 1, ni, nj))

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

Submission status: Wrong Answer

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

distance = INF

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

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    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] == ".":
            A[ni][nj] = "#"
            Q.append((dist + 1, ni, nj))

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

Submission status: Wrong Answer

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
  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: Wrong Answer

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor
from scipy.ndimage import distance_transform_cdt
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')


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 A[h, w] == b'#' or seen[h, w]:
            continue
        min_step = min(min_step, step(h, w))
        if k > 0:
            seen[h, w] = True
            que.append((h, w, k - 1))
print(min_step + 1)

Submission status: Wrong Answer

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])
        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: Wrong Answer

Solution code:
#!usr/bin/env python3
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

#A
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
#B
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

#C
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)])
    q_ = []
    while q:
        y,x = q.popleft()
        f = 0
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if a[ny][nx] == "#":
                    f = 1
                    continue
                if bfs[y][x] < k:
                    if bfs[ny][nx] < 0:
                        bfs[ny][nx] = bfs[y][x]+1
                        q.append((ny,nx))
        if f:
            q_.append((y,x))
    ans = float("inf")
    for y,x in q_:
        ans = min(ans, y, h-1-y, x, w-1-x)
    print(math.ceil(ans/k)+1)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
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

#A
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
#B
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

#C
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)])
    q_ = deque()
    while q:
        y,x = q.popleft()
        f = 0
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if a[ny][nx] == "#":
                    f = 1
                    continue
                if bfs[y][x] < k:
                    if bfs[ny][nx] < 0:
                        bfs[ny][nx] = bfs[y][x]+1
                        q.append((ny,nx))
        if f:
            q_.append((y,x))
    for y in range(h):
        for x in range(w):
            if bfs[y][x] >= 0:
                bfs[y][x] = k-1

    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 bfs[ny][nx] < 0:
                    bfs[ny][nx] = bfs[y][x]+1
                    q_.append((ny,nx))
    ans = float("inf")
    for y in range(h):
        if bfs[y][0] < ans:
            ans = bfs[y][0]
        if bfs[y][-1] < ans:
            ans = bfs[y][-1]
    for x in range(w):
        if bfs[0][x] < ans:
            ans = bfs[0][x]
        if bfs[-1][x] < ans:
            ans = bfs[-1][x]
    print(ans//k+1)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
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

#A
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
#B
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

#C
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)])
    q_ = deque()
    while q:
        y,x = q.popleft()
        f = 0
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if a[ny][nx] == "#":
                    f = 1
                    continue
                if bfs[y][x] < k:
                    if bfs[ny][nx] < 0:
                        bfs[ny][nx] = bfs[y][x]+1
                        q.append((ny,nx))
        if f:
            q_.append((y,x))
    for y in range(h):
        for x in range(w):
            if bfs[y][x] >= 0:
                bfs[y][x] = 2*k-1

    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 bfs[ny][nx] < 0:
                    bfs[ny][nx] = bfs[y][x]+1
                    q_.append((ny,nx))
    ans = float("inf")
    for y in range(h):
        if bfs[y][0] < ans:
            ans = bfs[y][0]
        if bfs[y][-1] < ans:
            ans = bfs[y][-1]
    for x in range(w):
        if bfs[0][x] < ans:
            ans = bfs[0][x]
        if bfs[-1][x] < ans:
            ans = bfs[-1][x]
    print(ans//k)
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
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

#A
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
#B
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

#C
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)])
    q_ = deque()
    while q:
        y,x = q.popleft()
        f = 0
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if a[ny][nx] == "#":
                    f = 1
                    continue
                if bfs[y][x] < k:
                    if bfs[ny][nx] < 0:
                        bfs[ny][nx] = bfs[y][x]+1
                        q.append((ny,nx))
        if f:
            q_.append((y,x))

    for y in range(h):
        for x in range(w):
            if bfs[y][x] >= 0:
                if y in (0,h-1) or x in (0,w-1):
                    print(1)
                    return
                bfs[y][x] = k

    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 bfs[ny][nx] < 0:
                    bfs[ny][nx] = bfs[y][x]+1
                    q_.append((ny,nx))
    ans = float("inf")
    for y in range(h):
        if bfs[y][0] < ans:
            ans = bfs[y][0]
        if bfs[y][-1] < ans:
            ans = bfs[y][-1]

    for x in range(w):
        if bfs[0][x] < ans:
            ans = bfs[0][x]
        if bfs[-1][x] < ans:
            ans = bfs[-1][x]
    print(math.ceil(ans/k))
    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Wrong Answer

Solution code:
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 x,dx in itertools.product(q,dxs):
        y = x+dx
        if A[y] == '#':
            continue
        if y in visited:
            continue
        visited.add(y)
        qq.append(y)
    q = qq

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

# 初日以外は何も気にせず動けるとしてよい。初日に到達可能な場所のうち、最もゴールに近いものはどこか

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 in dxs:
        for x in 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 = x//(W+2)
    col = x%(W+2)
    d = min(row-1,W-row,col-1,H-col)
    if nearest > d:
        nearest = d

answer = 1 + (nearest+K-1)//K
print(answer)

Submission status: Wrong Answer

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(4):
            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 B[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 B[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 B[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)