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 defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
flg = 0
for a in range(h):
    for b in range(w):
        if A[a][b] == 'S':
            sy, sx = a, b
            A[sy][sx] = 0
            flg = 1
            break
    if flg:
        break

q = deque([(sy, sx)])
ans = 1 + min((sy + k - 1) // k, (h - sy + k) // k,
              (sx + k - 1) // k, (w - sx + k) // k)
while q:
    y, x = q.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + i, y + j
        if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == '.':
            A[ny][nx] = A[y][x] + 1
            ans = min(ans, min((ny - 1) // k, (h - ny - 2) // k,
                               (nx - 1) // k, (w - nx - 2) // k))
            if A[ny][nx] < k:
                q += [(ny, nx)]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
flg = 0
for a in range(h):
    for b in range(w):
        if A[a][b] == 'S':
            sy, sx = a, b
            A[sy][sx] = 0
            flg = 1
            break
    if flg:
        break

q = deque([(sy, sx)])
ans = 1 + min((sy + k - 1) // k, (h - sy + k) // k,
              (sx + k - 1) // k, (w - sx + k) // k)
while q:
    y, x = q.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + i, y + j
        if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == '.':
            A[ny][nx] = A[y][x] + 1
            ans = min(ans, min((ny - 1) // k, (h - ny) // k,
                               (nx - 1) // k, (w - nx) // k))
            if A[ny][nx] < k:
                q += [(ny, nx)]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
flg = 0
for a in range(h):
    for b in range(w):
        if A[a][b] == 'S':
            sy, sx = a, b
            A[sy][sx] = 0
            flg = 1
            break
    if flg:
        break

q = deque([(sy, sx)])
ans = 1 + min((sy + k - 1) // k, (h - sy + k) // k,
              (sx + k - 1) // k, (w - sx + k) // k)
while q:
    y, x = q.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nxt_y, nxt_x = y + i, x + j
        if A[nxt_y][nxt_x] == '.':
            if nxt_y == 0 or nxt_y == h - 1 or nxt_x == 0 or nxt_x == w - 1:
                print(1)
                exit()
            ans = min(ans, 1 + min((nxt_y + k - 1) // k, (h - nxt_y + k) // k,
                               (nxt_x + k - 1) // k, (w - nxt_x + k) // k))
            A[nxt_y][nxt_x] = A[y][x] + 1
            if A[nxt_y][nxt_x] < k:
                q += [(nxt_y, nxt_x)]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
flg = 0
for a in range(h):
    for b in range(w):
        if A[a][b] == 'S':
            sy, sx = a, b
            A[sy][sx] = 0
            flg = 1
            break
    if flg:
        break

q = [(sy, sx)]
ans = 1 + min((sy + k - 1) // k, (h - sy + k) // k,
              (sx + k - 1) // k, (w - sx + k) // k)
while q:
    y, x = q.pop()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nxt_y, nxt_x = y + i, x + j
        if A[nxt_y][nxt_x] == '.':
            if nxt_y == 0 or nxt_y == h - 1 or nxt_x == 0 or nxt_x == w - 1:
                print(1)
                exit()
            ans = min(ans, 1 + min((nxt_y + k - 1) // k, (h - nxt_y + k) // k,
                               (nxt_x + k - 1) // k, (w - nxt_x + k) // k))
            A[nxt_y][nxt_x] = A[y][x] + 1
            if A[nxt_y][nxt_x] < k:
                q += [(nxt_y, nxt_x)]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
flg = 0
for a in range(h):
    for b in range(w):
        if A[a][b] == 'S':
            sy, sx = a, b
            flg = 1
            break
    if flg:
        break

q = [(sy, sx)]
ans = 1 + min((sy + k - 1) // k, (h - sy + k) // k,
              (sx + k - 1) // k, (w - sx + k) // k)
while q:
    y, x = q.pop()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nxt_y, nxt_x = y + i, x + j
        if A[nxt_y][nxt_x] == '.':
            if nxt_y == 0 or nxt_y == h - 1 or nxt_x == 0 or nxt_x == w - 1:
                print(1)
                exit()
            ans = min(ans, 1 + min((nxt_y + k - 1) // k, (h - nxt_y + k) // k,
                               (nxt_x + k - 1) // k, (w - nxt_x + k) // k))
            q += [(nxt_y, nxt_x)]
            A[nxt_y][nxt_x] = '#'


print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
h,w,k = map(int,input().split())
l = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == "S":
            s = [0,[i,j],0,0]
    l.append(a)
ans = h*w
dp = [[[h*w,0,0] for i in range(w)] for i in range(h)]
dp[s[1][0]][s[1][1]] = [0,0,0]
d = [s]
b = [[0,1],[1,0],[-1,0],[0,-1]]
heapq.heapify(d)
while len(d):
    spell1,now,steps1,op1 = heapq.heappop(d)
    if ans < spell1:
        break
    for i in b:
        spell = spell1
        steps = steps1
        op = op1
        #print(now[0]+i[0],now[1]+i[1])
        nex = [now[0]+i[0],now[1]+i[1]]
        if l[nex[0]][nex[1]] == ".":
            if steps > 0:
                steps -= 1
            else:
                spell += 1
                steps += k-1
                op += k
        else:
            if op > 0:
                if steps > 0:
                    steps -= 1
                    op -= 1
                else:
                    op -= 1
                    steps += k-1
                    spell += 1
            else:
                if steps == 0:
                    steps += k-1
                    spell += 2
                    op += k-1
                else:
                    op += k-1
                    steps += k-1
                    spell += 1
        if nex[0] == 0 or nex[0] == h-1 or nex[1] == 0 or nex[1] == w-1:
            ans = min(ans,spell)
        else:
            dp0 = dp[nex[0]][nex[1]]
            if dp0[0] > spell:
                dp[nex[0]][nex[1]] = [spell,steps,op]
                heapq.heappush(d,[spell,nex,steps,op])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
h,w,k = map(int,input().split())
l = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == "S":
            s = [0,[i,j],0,0]
    l.append(a)
ans = h*w
dp = [[[h*w,0,0] for i in range(w)] for i in range(h)]
dp[s[1][0]][s[1][1]] = [0,0,0]
d = [s]
b = [[0,1],[1,0],[-1,0],[0,-1]]
heapq.heapify(d)
while len(d):
    spell1,now,steps1,op1 = heapq.heappop(d)
    if ans < spell1:
        break
    for i in b:
        spell = spell1
        steps = steps1
        op = op1
        #print(now[0]+i[0],now[1]+i[1])
        nex = [now[0]+i[0],now[1]+i[1]]
        if l[nex[0]][nex[1]] == ".":
            if steps > 0:
                steps -= 1
            else:
                spell += 1
                steps += k-1
        else:
            if op > 0:
                if steps > 0:
                    steps -= 1
                    op -= 1
                else:
                    op -= 1
                    steps += k-1
                    spell += 1
            else:
                if steps == 0:
                    steps += k-1
                    spell += 2
                    op += k-1
                else:
                    op += k-1
                    steps += k-1
                    spell += 1
        if nex[0] == 0 or nex[0] == h-1 or nex[1] == 0 or nex[1] == w-1:
            ans = min(ans,spell)
        else:
            dp0 = dp[nex[0]][nex[1]]
            if dp0[0] > spell:
                dp[nex[0]][nex[1]] = [spell,steps,op]
                heapq.heappush(d,[spell,nex,steps,op])
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

def calc(x,y):
  cnt1=(x+k-1)//k
  cnt2=(w-1-x+k-1)//k
  cnt3=(y+k-1)//k
  cnt4=(h-1-y+k-1)//k
  return min(cnt1,cnt2,cnt3,cnt4)

h,w,k=map(int,input().split())
boards=[list(input()) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if boards[i][j]=='S':
      sx=j
      sy=i
      break
q=collections.deque()
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
q.append((sx,sy))
ans=1+calc(sx,sy)
while 1:
  if len(q)==0:
    break
  tx,ty=q.popleft()
  ans=min(ans,1+calc(tx,ty))
  if tx!=0 and boards[ty][tx-1]!='#' and checked[ty][tx-1]==0:
    checked[ty][tx-1]=1
    q.append((tx-1,ty))
  if tx!=w-1 and boards[ty][tx+1]!='#' and checked[ty][tx+1]==0:
    checked[ty][tx+1]=1
    q.append((tx+1,ty))
  if ty!=0 and boards[ty-1][tx]!='#' and checked[ty-1][tx]==0:
    checked[ty-1][tx]=1
    q.append((tx,ty-1))
  if ty!=h-1 and boards[ty+1][tx]!='#' and checked[ty+1][tx]==0:
    checked[ty+1][tx]=1
    q.append((tx,ty+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

def calc(x,y):
  cnt1=(x+k-1)//k
  cnt2=(w-x+k-1)//k
  cnt3=(y+k-1)//k
  cnt4=(h-y+k-1)//k
  return min(cnt1,cnt2,cnt3,cnt4)

h,w,k=map(int,input().split())
boards=[list(input()) for _ in range(h)]
sx=0
sy=0
for i in range(h):
  for j in range(w):
    if boards[i][j]=='S':
      sx=j
      sy=i
      break
q=collections.deque()
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
q.append((sx,sy))
ans=1+calc(sx,sy)
while 1:
  if len(q)==0:
    break
  tx,ty=q.popleft()
  ans=min(ans,1+calc(tx,ty))
  if tx!=0 and boards[ty][tx-1]!='#' and checked[ty][tx-1]==0:
    checked[ty][tx-1]=1
    q.append((tx-1,ty))
  if tx!=w-1 and boards[ty][tx+1]!='#' and checked[ty][tx+1]==0:
    checked[ty][tx+1]=1
    q.append((tx+1,ty))
  if ty!=0 and boards[ty-1][tx]!='#' and checked[ty-1][tx]==0:
    checked[ty-1][tx]=1
    q.append((tx,ty-1))
  if ty!=h-1 and boards[ty+1][tx]!='#' and checked[ty+1][tx]==0:
    checked[ty+1][tx]=1
    q.append((tx,ty+1))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W,K = map(int,input().split())
    room = [list(map(str,input())) for _ in range(H)]
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            if room[i][j] == "S":
                sx,sy = i,j
                dist[i][j] = 0
    
    ans = min(sx,H-sx-1,sy,W-sy-1)
    q = deque([(sx,sy)])
    c = 0
    while (q and c!=K):
        c += 1
        x,y = q.pop()
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if (0<nx<H-1 and 0<ny<W-1):
                if (room[nx][ny] == "." and dist[nx][ny] == -1):
                    dist[nx][ny] = 1
                    ans = min(ans,nx,H-nx-1,ny,W-ny-1)
                    q.append((nx,ny))
            else:
                if room[nx][ny] == ".":
                    print(1)
                    exit()
                
    print(2+(ans-1)//K)            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W,K = map(int,input().split())
    room = [list(map(str,input())) for _ in range(H)]
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            if room[i][j] == "S":
                sx,sy = i,j
                dist[i][j] = 0
    
    ans = min(sx,H-sx-1,sy,W-sy-1)
    q = deque([(sx,sy)])
    c = 0
    while (q and c!=K):
        c += 1
        x,y = q.pop()
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if (0<nx<H-1 and 0<ny<W-1):
                if (room[nx][ny] == "." and dist[nx][ny] == -1):
                    dist[nx][ny] = 1
                    ans = min(ans,nx,H-nx-1,ny,W-ny-1)
                    q.append((nx,ny))
            else:
                if room[nx][ny] == ".":
                    print(1)
                    exit()
                
    print(-(-ans//K)+1)            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W,K = map(int,input().split())
    room = [list(map(str,input())) for _ in range(H)]
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            if room[i][j] == "S":
                sx,sy = i,j
                dist[i][j] = 0
    
    ans = min(sx,H-sx-1,sy,W-sy-1)
    q = deque([(sx,sy)])
    while q:
        x,y = q.pop()
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if (0<nx<H-1 and 0<ny<W-1):
                if (room[nx][ny] == "." and dist[nx][ny] == -1):
                    dist[nx][ny] = 1
                    ans = min(ans,nx,H-nx-1,ny,W-ny-1)
                    q.append((nx,ny))
            else:
                if room[nx][ny] == ".":
                    print(1)
                    exit()
                
    print(-(-ans//K)+1)            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W,K = map(int,input().split())
    room = [list(map(str,input())) for _ in range(H)]
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            if room[i][j] == "S":
                sx,sy = i,j
                dist[i][j] = 0
    
    if (sx == 0 or sx == H-1 or sy == 0 or sy == W-1):
        print(0)
        exit()
                
    q = deque([(sx,sy)])
    cs = [(sx,sy)]
    while q:
        x,y = q.pop()
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if (0<=nx<H and 0<=ny<W and room[nx][ny] == "." and dist[nx][ny] == -1):
                if (nx == 0 or nx == H-1 or ny == 0 or ny == W-1):
                    print(1)
                    exit()
                else:
                    dist[nx][ny] = dist[x][y] + 1
                    cs.append((nx,ny))
                    if dist[nx][ny] != K:
                        q.append((nx,ny))

    ans = 10**3
    for x,y in cs:
        ans = min(ans,-(-x//K),-(-(H-1-x)//K),-(-y//K),-(-(W-1-y)//K))
        
    print(ans+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque

def main():
    H,W,K = map(int,input().split())
    room = [list(map(str,input())) for _ in range(H)]
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            if room[i][j] == "S":
                sx,sy = i,j
                dist[i][j] = 0
                
    q = deque([(sx,sy)])
    cs = [(sx,sy)]
    while q:
        x,y = q.pop()
        dx,dy = [1,0,-1,0],[0,1,0,-1]
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if (0<=nx<H and 0<=ny<W and room[nx][ny] == "." and dist[nx][ny] == -1):
                if (nx == 0 or nx == H-1 or ny == 0 or ny == W-1):
                    print(1)
                    exit()
                else:
                    dist[nx][ny] = dist[x][y] + 1
                    cs.append((nx,ny))
                    if dist[nx][ny] != K:
                        q.append((nx,ny))

    ans = 10**3
    for x,y in cs:
        ans = min(ans,-(-x//K),-(-(H-1-x)//K),-(-y//K),-(-(W-1-y)//K))
        
    print(ans+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
a=[list(input())for i in range(h)]
b=[[1]*w for i in range(h)]
c=0
for i in range(h):
    if c:
        break
    for j in range(w):
        if a[i][j]=="S":
            c=1
            p=[i,j]
            b[i][j]=0
def f(x,y):
    return min(x,w-x-1,y,h-y-1)
an=f(p[0],p[1])
q=[p]
c=0
while q and c!=k:
    c+=1
    d=[]
    x=[0,0,1,-1]
    y=[1,-1,0,0]
    for i,j in q:
        for s,t in zip(x,y):
            if 0<i+s<h-1 and 0<j+t<w-1:
                if b[i+s][j+t]:
                    if a[i+s][j+t]==".":
                        an=min(an,f(i+s,j+t))
                        b[i+s][j+t]=0
                        d.append([i+s,j+t])
            else:
                if a[i+s][j+t]==".":
                     print(1)
                     exit()
    q=d[::]
print(2+(an-1)//k)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
a=[list(input())for i in range(h)]
b=[[1]*w for i in range(h)]
c=0
for i in range(h):
    if c:
        break
    for j in range(w):
        if a[i][j]=="S":
            c=1
            p=[i,j]
            b[i][j]=0
def f(x,y):
    return min(x,w-x-1,y,h-y-1)
an=f(p[0],p[1])
q=[p]
c=0
while q and c!=k:
    d=[]
    x=[0,0,1,-1]
    y=[1,-1,0,0]
    for i,j in q:
        for s,t in zip(x,y):
            if 0<i+s<h-1 and 0<j+t<w-1:
                if b[i+s][j+t]:
                    if a[i+s][j+t]==".":
                        an=min(an,f(i+s,j+t))
                        b[i+s][j+t]=0
                        d.append([i+s,j+t])
            else:
                if a[i+s][j+t]==".":
                     print(1)
                     exit()
    q=d[::]
print(2+(an-1)//k)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
a=[list(input())for i in range(h)]
b=[[1]*w for i in range(h)]
c=0
for i in range(h):
    if c:
        break
    for j in range(w):
        if a[i][j]=="S":
            c=1
            p=[i,j]
            b[i][j]=0
def f(x,y):
    return min(x,w-y-1,y,h-x-1)
an=f(p[0],p[1])
q=[p]
c=0
while q and c!=k:
    d=[]
    x=[0,0,1,-1]
    y=[1,-1,0,0]
    for i,j in q:
        for s,t in zip(x,y):
            if 0<=i+s<h and 0<=j+t<w:
                if b[i+s][j+t]:
                    if a[i+s][j+t]==".":
                        an=min(an,f(i+s,j+t))
                        b[i+s][j+t]=0
                        d.append([i+s,j+t])
            else:
                print(1)
                exit()
    q=d[::]
print(2+(an-1)//k)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
a=[list(input())for i in range(h)]
b=[[1]*w for i in range(h)]
c=0
for i in range(h):
    if c:
        break
    for j in range(w):
        if a[i][j]=="S":
            c=1
            p=[i,j]
            b[i][j]=0
def f(x,y):
    return min(x,w-x-1,y,h-y-1)
an=f(p[0],p[1])
q=[p]
c=0
while q and c!=k:
    d=[]
    x=[0,0,1,-1]
    y=[1,-1,0,0]
    for i,j in q:
        for s,t in zip(x,y):
            if 0<=i+s<h and 0<=j+t<w:
                if b[i+s][j+t]:
                    if a[i+s][j+t]==".":
                        an=min(an,f(i+s,j+t))
                        b[i+s][j+t]=0
                        d.append([i+s,j+t])
            else:
                print(1)
                exit()
    q=d[::]
print(2+(an-1)//k)

Submission status: Wrong Answer

Solution code:
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

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

b = "#"
r = "."

for i in range(H):
  for j in range(W):
    if A[i][j] == b:
      A[i][j] = -1
    elif A[i][j] == r:
      A[i][j] = 0
    else:
      A[i][j] = 0
      S = [i, j]

g = gridMan(A)
g.makeWall()

L, r = g.dist(S)

ans = 10 ** 10
for i in range(H):
  for j in range(W):
    if 0 <= g.L[i + 1][j + 1] and g.L[i + 1][j + 1] <= K:
      t = min(i, j, H - i - 1, W - j - 1)
      if t == 0:
        print(1)
        exit()
      t = (t + K - 1) // K
      ans = min(ans, t)

print(ans + 1)

Submission status: Wrong Answer

Solution code:
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):
#    debug_print(maze)
    distance = [[inf]*w for _ in range(h)]
    def bfs():
        queue = []
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#' and distance[ny][nx] == inf):
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)
#    print(D)
    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
from collections import deque
def resolve():
    h,w,k=map(int,input().split())
    G=[list(input()) for _ in range(h)]
    D=[(1,0),(-1,0),(0,1),(0,-1)]
    for i,j in product(range(h),range(w)):
        if(G[i][j]=='S'):
            i0,j0=i,j
            break

    dist=[[INF]*w for _ in range(h)]
    dist[i0][j0]=0
    # BFS
    Q=deque([(i0,j0)])
    while(Q):
        i,j=Q.popleft()
        for di,dj in D:
            ni=i+di; nj=j+dj
            if(not (0<=ni<h and 0<=nj<w)): continue
            if(dist[ni][nj]!=INF or G[ni][nj]=='#'): continue
            dist[ni][nj]=dist[i][j]+1
            Q.append((ni,nj))

    print(dist)

    # 後は距離が k 以下の点から一直線に外に向かえばよい
    ans=INF
    for i,j in product(range(h),range(w)):
        if(dist[i][j]<=k):
            d=min(i,j,h-i-1,w-j-1)
            if(d==0):
                print(1)
                return
            else:
                ans=min(ans,2+(d-1)//k)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
from collections import deque
def resolve():
    h,w,k=map(int,input().split())
    G=[list(input()) for _ in range(h)]
    D=[(1,0),(-1,0),(0,1),(0,-1)]
    for i,j in product(range(h),range(w)):
        if(G[i][j]=='S'):
            i0,j0=i,j
            break

    dist=[[INF]*w for _ in range(h)]
    dist[i0][j0]=0
    # BFS
    Q=deque([(i0,j0)])
    while(Q):
        i,j=Q.popleft()
        for di,dj in D:
            ni=i+di; nj=j+dj
            if(not (0<=ni<h and 0<=nj<w)): continue
            if(dist[ni][nj]!=INF or G[ni][nj]=='#'): continue
            dist[ni][nj]=dist[i][j]+1
            Q.append((ni,nj))

    # 後は距離が k 以下の点から一直線に外に向かえばよい
    ans=INF
    for i,j in product(range(h),range(w)):
        if(dist[i][j]<=k):
            d=min(i,j,h-i-1,w-i-1)
            if(d==0):
                print(1)
                return
            else:
                ans=min(ans,2+(d-1)//k)
    print(ans)
resolve()