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:
# -*- coding: utf-8 -*-

import sys
import os
import math

H, W, K = map(int, input().split())
#print(H, W, K)

map = []
for s in sys.stdin:
    s = s.strip()
    map.append(s)
#print(map)

# search S
for i, row in enumerate(map):
    if 'S' in row:
        x = row.index('S')
        y = i
        break

# 初期値から行ける場所全てをPに列挙する
P = []
Q = []
Q.append((x, y, 0))
visited = [[False] * 800 for i in range(800)]
dist = [[0] * 800 for i in range(800)]

# short cut
if K > W // 2 or K > H // 2:
    is_walled = True
    for i in range(W):
        if map[0][i] == '.':
            is_walled = False
        if map[H - 1][i] == '.':
            is_walled = False
    for i in range(H):
        if map[i][0] == '.':
            is_walled = False
        if map[i][W-1] == '.':
            is_walled = False
    if is_walled:
        # shortcut end
        print(2)
        exit()


def is_accessible(x, y):
    if 0 <= x <= W-1 and 0 <= y <= H-1 and not visited[y][x] and map[y][x] == '.':
        return True
    else:
        return False

while Q:
    px, py, d = Q.pop(0)
    P.append((px, py, d))
    visited[py][px] = True
    dist[py][px] = d

    if d < K:
        # 上下左右
        if is_accessible(px+1, py):
            Q.append((px+1, py, d+1))
        if is_accessible(px-1, py):
            Q.append((px-1, py, d+1))
        if is_accessible(px, py+1):
            Q.append((px, py+1, d+1))
        if is_accessible(px, py-1):
            Q.append((px, py-1, d+1))

#print(P)
min_dist = 10000
min_dist_p = None
for p in P:
    # その点から上下左右に向かったときの最薄の壁の厚さ
    x = p[0]
    y = p[1]
    dist_to_wall = min(x, y, W - x - 1, H - y - 1)
    #print('p', p, dist_to_wall)
    if dist_to_wall < min_dist:
        min_dist = dist_to_wall
        min_dist_p = p

x = min_dist_p[0]
y = min_dist_p[1]
#print('min p', min_dist_p, 'dist', min_dist, 'そこまでの距離', dist[y][x])

# 1発目でそこに行き、あとは魔法して進むのみ
#print('壁の厚さ', min_dist)
magic_num = math.ceil(min_dist / K)
print(int(magic_num) + 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

H, W, K = map(int, input().split())
#print(H, W, K)

map = []
for s in sys.stdin:
    s = s.strip()
    map.append(list(s))
#print(map)

# search S
for i, row in enumerate(map):
    if 'S' in row:
        x = row.index('S')
        y = i
        break

# 初期値から行ける場所全てをPに列挙する
P = []
Q = []
Q.append((x, y, 0))
visited = [[False] * 800 for i in range(800)]
dist = [[0] * 800 for i in range(800)]

# short cut
if K > W // 2 or K > H // 2:
    is_walled = True
    for i in range(W):
        if map[0][i] == '.':
            is_walled = False
        if map[H - 1][i] == '.':
            is_walled = False
    for i in range(H):
        if map[i][0] == '.':
            is_walled = False
        if map[i][W-1] == '.':
            is_walled = False
    if is_walled:
        # shortcut end
        print(2)
        exit()


def is_accessible(x, y):
    if 0 <= x <= W-1 and 0 <= y <= H-1 and not visited[y][x] and map[y][x] == '.':
        return True
    else:
        return False

while Q:
    px, py, d = Q.pop(0)
    P.append((px, py, d))
    visited[py][px] = True
    dist[py][px] = d

    if d < K:
        # 上下左右
        if is_accessible(px+1, py):
            Q.append((px+1, py, d+1))
        if is_accessible(px-1, py):
            Q.append((px-1, py, d+1))
        if is_accessible(px, py+1):
            Q.append((px, py+1, d+1))
        if is_accessible(px, py-1):
            Q.append((px, py-1, d+1))

#print(P)
min_dist = 10000
min_dist_p = None
for p in P:
    # その点から上下左右に向かったときの最薄の壁の厚さ
    x = p[0]
    y = p[1]
    dist_to_wall = min(x, y, W - x - 1, H - y - 1)
    #print('p', p, dist_to_wall)
    if dist_to_wall < min_dist:
        min_dist = dist_to_wall
        min_dist_p = p

x = min_dist_p[0]
y = min_dist_p[1]
#print('min p', min_dist_p, 'dist', min_dist, 'そこまでの距離', dist[y][x])

# 1発目でそこに行き、あとは魔法して進むのみ
#print('壁の厚さ', min_dist)
magic_num = math.ceil(min_dist / K)
print(int(magic_num) + 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

H, W, K = map(int, input().split())
#print(H, W, K)

map = []
for s in sys.stdin:
    s = s.strip()
    map.append(list(s))
#print(map)

# search S
for i, row in enumerate(map):
    if 'S' in row:
        x = row.index('S')
        y = i
        break

# 初期値から行ける場所全てをPに列挙する
P = []
Q = []
Q.append((x, y, 0))
visited = [[False] * 800 for i in range(800)]
dist = [[False] * 800 for i in range(800)]

def is_accessible(x, y):
    if 0 <= x <= W-1 and 0 <= y <= H-1 and not visited[y][x] and map[y][x] == '.':
        return True
    else:
        return False

while Q:
    px, py, d = Q.pop(0)
    P.append((px, py, d))
    visited[py][px] = True
    dist[py][px] = d

    if d < K:
        # 上下左右
        if is_accessible(px+1, py):
            Q.append((px+1, py, d+1))
        if is_accessible(px-1, py):
            Q.append((px-1, py, d+1))
        if is_accessible(px, py+1):
            Q.append((px, py+1, d+1))
        if is_accessible(px, py-1):
            Q.append((px, py-1, d+1))

#print(P)
min_dist = 10000
min_dist_p = None
for p in P:
    # その点から上下左右に向かったときの最薄の壁の厚さ
    x = p[0]
    y = p[1]
    dist_to_wall = min(x, y, W - x - 1, H - y - 1)
    #print('p', p, dist_to_wall)
    if dist_to_wall < min_dist:
        min_dist = dist_to_wall
        min_dist_p = p

x = min_dist_p[0]
y = min_dist_p[1]
#print('min p', min_dist_p, 'dist', min_dist, 'そこまでの距離', dist[y][x])

# 1発目でそこに行き、あとは魔法して進むのみ
#print('壁の厚さ', min_dist)
magic_num = math.ceil(min_dist / K)
print(int(magic_num) + 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

H, W, K = map(int, input().split())
#print(H, W, K)

map = []
for s in sys.stdin:
    s = s.strip()
    map.append(list(s))
#print(map)

# search S
for i, row in enumerate(map):
    if 'S' in row:
        x = row.index('S')
        y = i

# 初期値から行ける場所全てをPに列挙する
P = []
Q = []
Q.append((x, y, 0))
visited = [[False] * 800 for i in range(800)]
dist = [[False] * 800 for i in range(800)]

def is_accessible(x, y):
    if 0 <= x <= W-1 and 0 <= y <= H-1 and not visited[y][x] and map[y][x] == '.':
        return True
    else:
        return False

while Q:
    px, py, d = Q.pop(0)
    P.append((px, py, d))
    visited[py][px] = True
    dist[py][px] = d

    if d < K:
        # 上下左右
        if is_accessible(px+1, py):
            Q.append((px+1, py, d+1))
        if is_accessible(px-1, py):
            Q.append((px-1, py, d+1))
        if is_accessible(px, py+1):
            Q.append((px, py+1, d+1))
        if is_accessible(px, py-1):
            Q.append((px, py-1, d+1))

#print(P)
min_dist = 10000
min_dist_p = None
for p in P:
    # その点から上下左右に向かったときの最薄の壁の厚さ
    x = p[0]
    y = p[1]
    dist_to_wall = min(x, y, W - x - 1, H - y - 1)
    #print('p', p, dist_to_wall)
    if dist_to_wall < min_dist:
        min_dist = dist_to_wall
        min_dist_p = p

x = min_dist_p[0]
y = min_dist_p[1]
#print('min p', min_dist_p, 'dist', min_dist, 'そこまでの距離', dist[y][x])

# 1発目でそこに行き、あとは魔法して進むのみ
#print('壁の厚さ', min_dist)
magic_num = math.ceil(min_dist / K)
print(int(magic_num) + 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

H, W, K = map(int, input().split())
#print(H, W, K)

map = []
for s in sys.stdin:
    s = s.strip()
    map.append(list(s))
#print(map)

# search S
for i, row in enumerate(map):
    if 'S' in row:
        x = row.index('S')
        y = i

# 初期値から行ける場所全てをPに列挙する
P = []
Q = []
Q.append((x, y, 0))
visited = [[False] * 800 for i in range(800)]
dist = [[False] * 800 for i in range(800)]

def is_accessible(x, y):
    if 0 <= x <= W-1 and 0 <= y <= H-1 and not visited[y][x] and map[y][x] == '.':
        return True
    else:
        return False

while Q:
    px, py, d = Q.pop(0)
    P.append((px, py, d))
    visited[py][px] = True
    dist[py][px] = d

    if d < K:
        # 上下左右
        if is_accessible(px+1, py):
            Q.append((px+1, py, d+1))
        if is_accessible(px-1, py):
            Q.append((px-1, py, d+1))
        if is_accessible(px, py+1):
            Q.append((px, py+1, d+1))
        if is_accessible(px, py-1):
            Q.append((px, py-1, d+1))

#print(P)
min_dist = 10000
min_dist_p = None
for p in P:
    # その点から上下左右に向かったときの最薄の壁の厚さ
    x = p[0]
    y = p[1]
    dist_to_wall = min(x, y, W - x - 1, H - y - 1)
    #print('p', p, dist_to_wall)
    if dist_to_wall < min_dist:
        min_dist = dist_to_wall
        min_dist_p = p

x = min_dist_p[0]
y = min_dist_p[1]
#print('min p', min_dist_p, 'dist', min_dist, 'そこまでの距離', dist[y][x])

# 1発目でそこに行き、あとは魔法して進むのみ
#print('壁の厚さ', min_dist)
magic_num = math.ceil(min_dist / K)
print(magic_num + 1)

Submission status: Time Limit Exceeded

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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def dist(r, c):
    return min(r, H - r - 1, c, W - c - 1)

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

for r in range(H):
    for c in range(W):
        if A[r][c] == 'S':
            sr = r
            sc = c

dxy = [(1, 0), (0, -1), (-1, 0), (0, 1)]
pos = [(sr, sc)]
dic = {(sr, sc): K}
cnt = 0
ans = H * W
while 0 < len(pos):
    r0, c0 = pos[0]
    pos = pos[1:]
    d0 = dist(r0, c0)
    ans = min(ans, (d0 + K - 1) // K + 1)
    m0 = dic[(r0, c0)]
    if 0 < m0:
        m = m0 - 1
        for (dx, dy) in dxy:
            r = r0 + dy
            c = c0 + dx
            d = dist(r, c)
            if 0 <= r < H and 0 <= c < W and A[r][c] != '#' and (r, c) not in dic:
                pos.append((r, c))
                dic[(r, c)] = m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from random import *
from functools import reduce,partial
from time import time
from pprint import pprint

def readln():
    return list(map(int,input().split(' ')))

def identity(x):
    """Return the input itself."""
    return x

def constant(c):
    """Return an function which always
    returns the input constant c."""
    def const_function(const,*args):
        return const
    return partial(const_function,c)

def inc(c = 1):
    """Return a function which reads an input x and returns x + c as output.
    By default, c equals 1."""
    return lambda x: x + c

def add(*args):
    """Return the sum of the input."""
    def add2(x,y): return x + y
    return reduce(add2,args)

def mapv(f,*lst):
    """Return a vector of the result of map."""
    return list(map(f,*lst))

def vector(*args):
    """Return a vector of input parameters."""
    return args

def sequence(n,f = constant(0)):
    """Return a vector of length n, and initialize the i'th
    item with f(i).By default the vector will initialized with 0."""
    return [f(i) for i in range(0,n)]

def matrix(n,m,f = constant(0)):
    """Return a 2-dim vector which contains n vectors with length m.
    The j's item of vector i will be initialized by f(i,j).By default,
    the vector will be initialized with 0."""
    return [[f(i,j) for j in range(0,m)] for i in range(0,n)]

def flat(v):
    """Return a flat vector which contains the elements of v in their
    origin order.If the input is not a vector, return a vector which
    only contains the input."""
    if not isinstance(v,list): return [v]
    if not v: return []
    return reduce(add,mapv(flat,v))

def partition(v,f = identity):
    """Partition vector v by f(v[i]).
    e.g. partition([1,2,3,1,2,3],identity()) == {1:[1,1,1], 2:[2,2], 3:[3]}
    By default, the vector will be partitioned by identity function."""
    result = {}
    for item in v:
        key = f(item)
        s = result.get(key)
        if s:
            s.append(item)
        else:
            result.update({key:[item]})
    return result

def getValue(key):
    """Return a function which returns the value of key in a hash-map.
    If the key do not exist, it will throw an error."""
    return lambda x: x[key]

def mapValue(f,m):
    """Replace each value in hash-map m with f(value).
    Return the new hash-map."""
    res = {}
    for key in m:
        res.update({key: f(m[key])})
    return res

p = 1000000000 + 7

def calc(x,y):
    d = min(x,y,h-x-1,w-y-1)
    return d

def push(x,y,step):
    global s,ans
    if m[x][y] == '.':
        m[x][y] = 'O'
        s.append([x,y,step])
        ans = min(calc(x,y),ans)

h,w,k = readln()
m = [None for i in range(h)]
for i in range(h):
    s = input()
    m[i] = [s[j] for j in range(w)]

q = matrix(h,w)
s = [0]
for i in range(h):
    for j in range(w):
        if m[i][j] == 'S':
            s[0] = [i,j,0]
ans = calc(s[0][0],s[0][1])
for i in range(h*w):
    if i >= len(s):
        break
    x,y,step = s[i]
    if step == k:
        break
    if x > 0 : push(x-1,y,step+1)
    if x < h - 1 : push(x+1,y,step+1)
    if y > 0 : push(x,y-1,step+1)
    if y < w - 1 : push(x,y+1,step+1)
x,y,s = s[0]
ans = ans + k - 1
if calc(x,y) == 0:
    print(0)
else:
    print(ans//k + 1)

Submission status: Accepted

Solution code:
from collections import deque

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

D = [[1 for i in range(W)] for j in range(H)]

for x in range(H):
    for y in range(W):
        if S[x][y] == 'S':
            sx = x
            sy = y

D[sx][sy] = 0

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

ans = float('inf')

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

while len(q) != 0:
    x, y, cnt = q.popleft()
    if cnt > K:
        break
    tmp = min(x, y , H - x - 1, W - y - 1)
    if tmp != 0:
        tmp = (tmp - 1) // K
        tmp += 2
    else:
        tmp = 1
    ans = min(ans, tmp)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '#' and D[nx][ny]:
            D[nx][ny] = 0
            q.append([nx, ny, cnt + 1])

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
a=[input() for _ in range(h)]
s=(0,0)
for i in range(h*w):
    x,y=divmod(i,w)
    if a[x][y]=='S':
        s=(x,y)
        break
from collections import deque
todo=deque([s])
inf=float('inf')
seen=[[inf]*w for _ in range(h)]
seen[s[0]][s[1]]=0
while todo:
    (x,y)=todo.popleft()
    for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        nx=x+dx
        ny=y+dy
        if 0<=nx<h and 0<=ny<w and a[nx][ny]!='#' and seen[nx][ny]>seen[x][y]+1:
            seen[nx][ny]=seen[x][y]+1
            if seen[nx][ny]<k:todo.append((nx,ny))
ans=h*w
for i in range(h*w):
    x,y=divmod(i,w)
    if seen[x][y]==inf:continue
    tmp=min(x,y,h-x-1,w-y-1)
    tmp=(tmp+k-1)//k
    ans=min(ans,tmp)
print(ans+1)

Submission status: Accepted

Solution code:
def main(h,w,k,a):
  s=-1,-1
  for i in range(h):
    for j in range(w):
      if a[i][j]=='S':
        s=i,j
        break
    if s[0]!=-1:break
  inf=float('inf')
  da=[[inf]*w for _ in range(h)]
  da[s[0]][s[1]]=0
  todo=[s]
  dst=min(s[0],h-s[0]-1,s[1],w-s[1]-1)
  cnt=0
  while cnt<k and todo:
    ntodo=[]
    while todo:
      i,j=todo.pop()
      for di,dj in ((1,0),(-1,0),(0,1),(0,-1)):
        if 0<=i+di<h and 0<=j+dj<w and a[i+di][j+dj]=='.' and da[i+di][j+dj]>da[i][j]+1:
          da[i+di][j+dj]=da[i][j]+1
          ntodo.append((i+di,j+dj))
          dst=min(dst,i+di,h-i-di-1,j+dj,w-j-dj-1)
    cnt+=1
    todo=ntodo
  return 1+(dst+k-1)//k

h,w,k=map(int,input().split())
a=[input() for _ in range(h)]
print(main(h,w,k,a))

Submission status: Accepted

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[0] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[0] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = 1
        next_set = deque([(p, t)])
        while next_set:
            p, t = next_set.popleft()
            h, w = p
            for dh, dw in self.move:
                q = (h + dh, w + dw)
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                    continue
                if parent[q[0]][q[1]] != 0:
                    continue
                if t >= K:
                    continue
                #### (debug code) ######
                # self.debug(start, goal, q, t)
                ########################
                if q == goal:
                    return t + 1
                parent[q[0]][q[1]] = 1
                next_set.append((q, t + 1))
        return parent

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


###########################################################

from collections import deque
import sys
from math import ceil
import marshal
input = sys.stdin.readline



road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W, K = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)

grid = []
for h in range(H):
    grid.append(input().rstrip())
    for w, s in enumerate(grid[-1]):
        if s == "S":
            start = (h,w)
g = Grid(H, W, grid, (road, wall))
visit = g.bfs(start=start)
res = float("inf")
for h in range(H):
    for w in range(W):
        if visit[h][w]:
            res = min(ceil(h/K)+1,ceil(w/K)+1,ceil((H-1-h)/K)+1,ceil((W-1-w)/K)+1,res)
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def bfs():
    q = deque([(sx, sy)])
    dist = [[-1]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and A[nx][ny]=='.' and dist[nx][ny]==-1:
                dist[nx][ny] = dist[x][y]+1
                q.append((nx, ny))
    
    return dist

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

for i in range(H):
    for j in range(W):
        if A[i][j]=='S':
            sx, sy = i, j

dist = bfs()
ans = 10**18

for i in range(H):
    for j in range(W):
        if 0<=dist[i][j]<=K:
            ans = min(ans, 1+(min(i, j, H-1-i, W-1-j)+K-1)//K)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
a = []
for i in range(h):
    t = ins()
    a.append(t)
    v = t.find('S')
    if v>=0:
        s = (i,v)
if h==w==k==-3:
    3/0
q = deque([(s[0],s[1],0)])
b = [[BIG]*w for i in range(h)]
b[s[0]][s[1]] = 0
mn = BIG
while len(q)>0:
    x,y,d = q.popleft()
    mn = min([ \
      mn,(x+k-1)//k,(h-1-x+k-1)//k,(y+k-1)//k,(w-1-y+k-1)//k])
    if d>=k:
        continue
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and a[xx][yy]!='#' and \
           b[xx][yy]==BIG:
            b[xx][yy] = d+1
            q.append((xx,yy,d+1))
print(mn+1)

Submission status: Accepted

Solution code:
from collections import deque
inf = 10 ** 9 + 7
h, w, k = map(int, input().split())
a = [list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "S":
            sx, sy = i, j
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
l = [[inf] * w for i in range(h)]
l[sx][sy] = 0
s = set()
s.add((sx, sy))
que = deque([[sx, sy]])
ans = inf
while que:
    x, y = que.popleft()
    if x == 0 or x == h - 1 or y == 0 or y == w - 1:
        ans = 1
        break
    if l[x][y] == k:
        continue
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        if nx < 0 or nx >= h or ny < 0 or ny >= w or a[nx][ny] == "#" or l[nx][ny] != inf:
            continue
        s.add((nx, ny))
        l[nx][ny] = l[x][y] + 1
        que.append([nx, ny])
for i in s:
    c = (min(i[0], h - i[0] - 1, i[1], w - i[1] - 1) + k - 1) // k + 1
    ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
from collections import *
H,W,K=map(int,input().split())
A=[list(input()) for i in range(H)]
SX,SY=0,0
for i in range(H):
  for j in range(W):
    if A[i][j]=='S':
      SX,SY=j,i
D=deque()
Z=set()
P=1
def qao(y,x):
  if min(x,y)==0 or x+1==W or y+1==H:
    print(P)
    exit()
  if (y,x) in Z:
    return False
  D.append((y,x))
  Z.add((y,x))
  return True

w4x=(1,0,-1,0)
w4y=(0,1,0,-1)
def bfs(F):
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(4):
      if A[v[0]+w4y[j]][v[1]+w4x[j]]=='.' or F:
        qao(v[0]+w4y[j],v[1]+w4x[j])

qao(SY,SX)
for i in range(K):
  bfs(0)
D=deque(Z)
while True:
  P+=1
  for i in range(K):
    bfs(1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。
from collections import deque
INF = float("inf")
H,W,K = map(int,input().split())
Room = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  for j in range(W):
    if temp[j] == "S":
      sx = i;sy =j
  Room.append(temp)
#print(sx,sy)
d = [(1,0),(-1,0),(0,1),(0,-1)]

R = [[INF]*W for _ in range(H)]
R[sx][sy] = 0
reach = set([])
reach.add((sx,sy))
Q = deque([[sx,sy]])
while Q:
  x,y = Q.popleft()
  if x==0 or x==H-1 or y==0 or y==W-1:
    print(1)
    exit()
  if R[x][y] == K:
    #L.add((x,y))
    #if stp == K:
    continue
  #stp +=1
  for i in range(4):
    nx = x+d[i][0]
    ny = y+d[i][1]
    #print(nx,ny)
    if nx<0 or nx>=H or ny<0 or ny>= W or Room[nx][ny] == "#" or R[nx][ny] != INF:
      continue
    reach.add((nx,ny))
    R[nx][ny] = R[x][y] + 1
    Q.append([nx, ny])
    #print(Q)

ans = INF

for t in reach:
  x,y = t[0],t[1]
  nokori = min(x,H-1-x,y,W-1-y)
  step = (nokori+K-1)//K + 1 #1は最初のステップ
  ans = min(ans,step)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, A):
    for i in range(H):
        for j in range(W):
            if A[i][j] == 'S':
                s = (i, j)
    from collections import deque

    q = deque([s])
    d = [[None] * W for _ in range(H)]
    d[s[0]][s[1]] = 0

    ans = INF
    while q:
        x, y = q.popleft()
        ans = min(ans, min(abs(x), abs(x-H+1), abs(y), abs(y-W+1)))
        c = d[x][y]
        if c + 1 > K:
            continue
        for vx, vy in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] == '#':
                continue
            if d[vx][vy] is not None:
                continue
            q.append((vx, vy))
            d[vx][vy] = c + 1

    return 1 + -(-ans // K)


def main():
    H, W, K = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, A):
    for i in range(H):
        for j in range(W):
            if A[i][j] == 'S':
                s = (i, j)
    from collections import deque

    q = deque([s])
    d = [[None] * W for _ in range(H)]
    d[s[0]][s[1]] = 0

    ans = INF
    while q:
        x, y = q.popleft()
        t = min(abs(x), abs(x-H+1), abs(y), abs(y-W+1))
        ans = min(ans, t)
        for vx, vy in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] == '#':
                continue
            if d[vx][vy] is not None:
                continue

            c = d[x][y]
            if c + 1 <= K:
                q.append((vx, vy))
                d[vx][vy] = c + 1

    return 1 + -(-ans // K)


def main():
    H, W, K = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, A):
    for i in range(H):
        for j in range(W):
            if A[i][j] == 'S':
                s = (i, j)
    from collections import deque
    q = deque([s])
    d = [[None] * W for _ in range(H)]
    d[s[0]][s[1]] = 0
    r = [s]
    while q:
        x, y = q.popleft()
        for vx, vy in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] == '#':
                continue
            if d[vx][vy] is not None:
                continue
            c = d[x][y]
            if c + 1 <= K:
                q.append((vx, vy))
                d[vx][vy] = c + 1
                r.append((vx, vy))


    ans = INF
    for x, y in r:
        t = min(abs(x), abs(x-H+1), abs(y), abs(y-W+1))
        ans = min(ans, t)

    return 1 + -(-ans // K)


def main():
    H, W, K = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, K, A))


if __name__ == '__main__':
    main()