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: Accepted

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)])
    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 a[ny][nx] == "#":
                    continue
                if bfs[ny][nx] < 0:
                    bfs[ny][nx] = bfs[y][x]+1
                    if bfs[ny][nx] < k:
                        q.append((ny,nx))

    ans = float("inf")
    for y in range(h):
        for x in range(w):
            if bfs[y][x] >= 0:
                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: Accepted

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

nearest = 10**9
for x in visited:
    row,col = divmod(x,W+2)
    d = min(row-1,H-row,col-1,W-col)
    if nearest > d:
        nearest = d

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

Submission status: Accepted

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 dx,x in itertools.product(dxs,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,col = divmod(x,W+2)
    d = min(row-1,H-row,col-1,W-col)
    if nearest > d:
        nearest = d

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

Submission status: Accepted

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 dx,x in itertools.product(dxs,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,col = divmod(x,W+2)
    d = min(row-1,H-row,col-1,W-col)
    if nearest > d:
        nearest = d

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

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W, K = map(int, input().split())
    A = [input() for _ in range(H)]
    s = None
    for i in range(H):
        for j in range(W):
            if A[i][j] == "S":
                s = (i, j)
    q = deque()
    q.append((s[0], s[1], K))
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False] * W for _ in range(H)]
    visited[s[0]][s[1]] = True
    dst = float("inf")
    while(len(q)):
        i, j, m = q.popleft()
        dst = min(dst, min([i, j, H-1-i, W-1-j]))
        if m == 0:
            continue
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni < H and 0 <= nj < W:
                if A[ni][nj] == "." and not visited[ni][nj]:
                    q.append((ni, nj, m-1))
                    visited[ni][nj] = True
    ans = 1 - (-dst//K)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

H, W, K = map(int, input().split())
A = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    A_i_x = input()
    for j in range(W):
        A[i][j] = A_i_x[j]
        if A_i_x[j] == 'S':
            start_h = i
            start_w = j

dist_from_exit = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        dist_from_exit[i][j] = min(i, j, H - 1 - i, W - 1 - j)

queue = deque()
queue.append([start_h, start_w])
visited = [[-1 for _ in range(W)] for _ in range(H)]
visited[start_h][start_w] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
dist_left_cand = [dist_from_exit[start_h][start_w]]
while queue:
    h, w = queue.pop()
    for i in range(4):
        if 0 <= h + dy[i] <= H-1 and 0 <= w + dx[i] <= W-1:
            if visited[h + dy[i]][w + dx[i]] == -1 and A[h + dy[i]][w + dx[i]] == '.' and visited[h][w] < K:
                queue.appendleft([h + dy[i], w + dx[i]])
                visited[h + dy[i]][w + dx[i]] = visited[h][w] + 1
                dist_left_cand.append(dist_from_exit[h + dy[i]][w + dx[i]])

dist_left_min = min(dist_left_cand)
print((dist_left_min - 1) // K + 1 + 1)

Submission status: Accepted

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

    H, W, K = map(int, input().split())
    Ass = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

    def find2D(Sss, ch):
        for x, Ss in enumerate(Sss):
            y = Ss.find(ch)
            if y != -1:
                return (x, y)
        return (-1, -1)

    xS, yS = find2D(Ass, 'S')

    usedss = [[False]*(W+2) for _ in range(H+2)]
    usedss[xS][yS] = True
    vs = set([(xS, yS)])
    for _ in range(K):
        v2s = set()
        for x, y in vs:
            for dx, dy in dxys:
                x2, y2 = x+dx, y+dy
                if not usedss[x2][y2] and Ass[x2][y2] == '.':
                    usedss[x2][y2] = True
                    v2s.add((x2, y2))
        vs = v2s

    ans = 10**5
    for x in range(H):
        for y in range(W):
            if usedss[x+1][y+1]:
                dist = min(x, H-1-x, y, W-1-y)
                ans = min(ans, -(-dist//K)+1)
    print(ans)

solve()

Submission status: Accepted

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

def minCost(x,y):
    return min(start[X], W-1-start[X], start[Y], H-1-start[Y]) // K
search = []
searched = [[False for w in range(W)] for h in range(H)]
hq.heapify(search)
search.append((0, start[X], start[Y]))
vector = [(1,0),(-1,0),(0,1),(0,-1)]
max_x,min_x,max_y,min_y = 0,W-1,0,H-1
while len(search) > 0:
    cnt,x,y = hq.heappop(search)
    if x == 0 or x == W-1 or y == 0 or y == H-1:
        print(1)
        exit()
    if searched[y][x]:
        continue
    searched[y][x] = True
    max_x = max(max_x, x)
    min_x = min(min_x, x)
    max_y = max(max_y, y)
    min_y = min(min_y, y)
    for v in vector:
        newX,newY = x+v[X], y+v[Y]
        if not searched[newY][newX] and cnt < K and A[newY][newX] != "#":
            hq.heappush(search,(cnt+1,newX,newY))
dist = min(min_x, min_y, W-1-max_x, H-1-max_y)
print(1 + (dist+K-1)//K)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
b=[]
v=[[0]*w for _ in range(h)]
sh=0
sw=0
for i in range(h):
    s=list(input())
    b.append(s)
    
    if 'S' in s:
        sh=i
        sw=s.index('S')
#ans=10**18
d=[[0,1],[1,0],[-1,0],[0,-1]]

def bfs(y,x):
    ans=10**18
    c=0
    q=[(y,x)]
    v[y][x]=1
    ans=min(y,x,h-1-y,w-1-x)
    while c<k:
        p=[]
        c+=1
        for i,j in q:
            for di,dj in d:
                if 0<=i+di<h and 0<=j+dj<w and v[i+di][j+dj]!=1 and b[i+di][j+dj]!='#':
                    p.append((i+di,j+dj))
                    v[i+di][j+dj]=1
                    ans=min(ans,i+di,j+dj,h-1-i-di,w-1-j-dj)
        q=p
    return ans
ans=bfs(sh,sw)
print(1+(ans+k-1)//k)

Submission status: Accepted

Solution code:
from collections import deque
import math
h, w, k = [int(item) for item in input().split()]
field = ["O" * (w+2)]
for i in range(h):
    line = "O" + input().rstrip() + "O"
    field.append(line)
    if "S" in line:
        start = [i+1, line.index("S"), 0]
field.append("O" * (w+2))

dq = deque()
dq.append(start)
visited = [[0] * (w+2) for _ in range(h+2)]
visited[start[0]][start[1]] = 1
closest = 10**3 
while dq:
    x, y, d = dq.popleft()
    closest = min(closest, min(x-1, y-1, h-x, w-y))
    if closest == 0:
        break
    d += 1
    for dx, dy in [[1,0], [0,1], [-1,0], [0,-1]]:
        if field[x+dx][y+dy] == "." and visited[x+dx][y+dy] == 0 and d <= k:
            dq.append([x+dx, y+dy, d])
            visited[x+dx][y+dy] = 1
print(1 + int(math.ceil(closest / k)))

Submission status: Accepted

Solution code:
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                A[nh][nw] = '#'
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))

Submission status: Accepted

Solution code:
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    if A[h][w] == '#':
        continue
    A[h][w] = '#'
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W:
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))

Submission status: Accepted

Solution code:
import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == 'S':
        break
visited = A
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
sH = set([h])
sW = set([w])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and visited[h][w] != '#':
        visited[h][w] = '#'
        sH.add(h)
        sW.add(w)
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 +
      math.ceil(min([min(sH), H - 1 - max(sH),
                     min(sW), W - 1 - max(sW)]) / K))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
h,w,k=map(int, input().split())
s=[list(input()) for i in range(h)]
p=[[-1]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=='S':
            sta=(i,j)
np=[(1,0),(-1,0),(0,1),(0,-1)]
q={sta}
p[sta[0]][sta[1]]=0
step=0
while step<k and q:
    step+=1
    nq=set()
    while q:
        now=q.pop()
        for i,j in np:
            nx,ny=now[0]+i,now[1]+j
            if nx<0 or nx==h or ny<0 or ny==w:continue
            if s[nx][ny]=='.' and p[nx][ny]==-1:
                p[nx][ny]=step
                nq.add((nx,ny))
    q=nq.copy()

ans=10**9
for i in range(h):
    for j in range(w):
        if p[i][j]>=0:
            an=min(i,j,h-i-1,w-j-1)
            if ans>an:ans=an
print(-(-ans//k)+1)

Submission status: Accepted

Solution code:
from collections import deque
from math import ceil
H,W,K=map(int,input().split())
grid=[input() for i in range(H)]

for i in range(H):
  for j in range(W):
    if grid[i][j]=="S":
      S=(i,j)

stack=deque([(S[0],S[1],0)])
visited=[[False]*(W) for i in range(H)]
visited[S[0]][S[1]]=True
a=float("inf")
t=[-1,1]
while stack:
  i,j,m=stack.popleft()
  if m>K:
    break
  a=min(a,min(i,H-1-i,j,W-1-j))
  if a==0:
    break
  for s in t:
    if not visited[i+s][j] and grid[i+s][j]!="#":
      stack.append((i+s,j,m+1))
    if not visited[i][j+s] and grid[i][j+s]!="#":
      stack.append((i,j+s,m+1))
    visited[i+s][j]=True
    visited[i][j+s]=True
ans=1+ceil(a/K)
print(ans)

Submission status: Accepted

Solution code:
# https://beta.atcoder.jp/contests/agc014/submissions/1268295
from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


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

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

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

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

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

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
h,w,k = map(int,input().split())
a = []
for i in range(h):
  b = input()
  tmp = []
  for j in range(w):
    tmp.append(b[j])
    if b[j] == "S":
      sx = i
      sy = j
  a.append(tmp)
ma = [[0]*w for i in range(h)]
def dfs(x,y,z):
  if ma[x][y] == 1:
    return
  if z>k:
    return
  ma[x][y] = 1
  if x > 0 and a[x-1][y]== ".":
    que.append([x-1,y,z+1])
  if y > 0 and a[x][y-1]== ".":
    que.append([x,y-1,z+1])
  if x <h-1 and a[x+1][y]==".":
    que.append([x+1,y,z+1])
  if y <w-1 and a[x][y+1]==".":
    que.append([x,y+1,z+1])
que = deque([[sx,sy,0]])
while que:
  x,y,z = que.popleft()
  dfs(x,y,z)
ans = float("inf")
for i in range(h):
  for j in range(w):
    if ma[i][j] == 1:
      ans = min(ans,1+(h-i-1)//k+ (1 if (h-i-1)%k else 0),1+(w-j-1)//k+ (1 if (w-j-1)%k else 0),
               1+(i)//k+ (1 if (i)%k else 0),1+(j)//k+ (1 if (j)%k else 0))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque;h,w,k=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];r=9**20
for i in range(h):
 if'S'in m[i]:j=m[i].index('S');q=deque([[i,j]]);v[i][j]=0
while q:
 y,x=q.popleft();r=min(r,y,x,h-1-y,w-1-x)
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t+1and t<h and u+1and u<w and m[t][u]=='.'and v[t][u]<0and v[y][x]<k:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Submission status: Accepted

Solution code:
from collections import deque;h,w,k=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];r=9**20
for i in range(h):
 if'S'in m[i]:j=m[i].index('S');q=deque([[i,j]]);v[i][j]=0
while q:
 y,x=q.popleft();r=min(r,y,x,h-1-y,w-1-x)
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t>=0and t<h and u>=0and u<w and m[t][u]=='.'and v[t][u]<0and v[y][x]<k:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Submission status: Accepted

Solution code:
from collections import deque;h,w,k=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];r=9**20
for i in range(h):
 if'S'in m[i]:j=m[i].index('S');q=deque([[i,j]]);v[i][j]=0
while q:
 y,x=q.popleft()
 r=min(r,y,x,h-1-y,w-1-x)
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t>=0and t<h and u>=0and u<w and m[t][u]=='.'and v[t][u]<0and v[y][x]<k:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Submission status: Accepted

Solution code:
from collections import deque;h,w,k=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];r=9**20
for i in range(h):
 if'S'in m[i]:j=m[i].index('S');q=deque([[i,j]]);v[i][j]=0
while q:
 y,x=q.popleft()
 r=min(r,y,x,h-1-y,w-1-x)
 if v[y][x]==k:continue
 for i,j in([1,0],[-1,0],[0,1],[0,-1]):
  t,u=y+i,x+j
  if t>=0and t<h and u>=0and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
print(1-(-r//k))

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    h, w, k = map(int, input().split())
    maze = [input() for _ in range(h)]
    visited = [[-1]*w for _ in range(h)]
    for i in range(h):
        if 'S' in maze[i]:
            sy, sx = i, maze[i].index('S')
            break
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    r = 10**18
    while queue:
        y, x = queue.popleft()
        r = min(r, y, h-1-y, x, w-1-x)
        if visited[y][x] == k: continue
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if new_y < 0 or new_y >= h or new_x < 0 or new_x >= w: continue
            if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    print(1 -(-r // k))
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    from collections import deque
    h, w, k = map(int, input().split())
    maze = [input() for _ in range(h)]
    visited = [[-1]*w for j in range(h)]
    for i in range(h):
        if 'S' in maze[i]:
            sy, sx = i, maze[i].index('S')
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    r = 10**18
    while queue:
        y, x = queue.popleft()
        r = min(r, y, x, h-1-y, w-1-x)
        if visited[y][x] == k: continue
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if new_y < 0 or new_y >= h: continue
            if new_x < 0 or new_x >= w: continue
            if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
    print(1 -(-r // k))
if __name__ == '__main__':
    solve()