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:
import sys
from collections import deque
input = sys.stdin.readline
inf = 10**8
inf = 10
DX = (-1, 0, 1, 0, -1, -1, 1, 1)
DY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DX[:4]
DY = DY[:4]


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


dist = [[inf]*W for _ in range(H)]
node = []
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            node.append((i, j))
            dist[i][j] = 1

# まず一回普通にBFS
d = 0
memo = []
while d < K:
    nxt = []
    while node:
        x, y = node.pop()
        if x in (0, H - 1) or y in (0, W - 1):
            print(dist[x][y])
            exit()
        memo.append((x, y))
        for dx, dy in zip(DX, DY):
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            if grid[nx][ny] == "#":
                continue
            if dist[nx][ny] >= inf:
                dist[nx][ny] = 1
                nxt.append((nx, ny))
    d += 1
    node = nxt
memo.extend(node)

ans = inf
for x, y in memo:
    d = min(x, y, H - x - 1, W - y - 1)
    ans = min(ans, 1 + (d + K - 1) // K)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
inf = 10**8
inf = 10
DX = (-1, 0, 1, 0, -1, -1, 1, 1)
DY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DX[:4]
DY = DY[:4]


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


dist = [[inf]*W for _ in range(H)]
node = []
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            node.append((i, j))
            dist[i][j] = 1

# まず一回普通にBFS
d = 0
memo = []
while d < K:
    nxt = []
    while node:
        x, y = node.pop()
        if x in (0, H - 1) or y in (0, W - 1):
            print(dist[x][y])
            exit()
        memo.append((x, y))
        for dx, dy in zip(DX, DY):
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue
            if grid[nx][ny] == "#":
                continue
            if dist[nx][ny] >= inf:
                dist[nx][ny] = 1
                nxt.append((nx, ny))
    d += 1
    node = nxt
memo.extend(node)

ans = inf
for x, y in memo:
    tmp = min(x // K, (H - y) // K, y // K, (W - y) // K) + 1
    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

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,w-y)
    tmp=(tmp+k-1)//k
    ans=min(ans,tmp)
print(ans+1)

Submission status: Wrong Answer

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([[0,s]])
seen=[[0]*w for _ in range(h)]
seen[s[0]][s[1]]=1
while todo:
    d,(x,y)=todo.popleft()
    if d==k:continue
    for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        if 0<=x+dx<h and 0<=y+dy<w and a[x+dx][y+dy]!='#' and seen[x+dx][y+dy]==0:
            todo.append((d+1,(x+dx,y+dy)))
            seen[x+dx][y+dy]=1
ans=h*w
for i in range(h*w):
    x,y=divmod(i,w)
    if seen[x][y]==1:
        tmp=min(x,y,h-x,w-y)
        tmp=(tmp+k-1)//k
        ans=min(ans,tmp)
print(ans+1)

Submission status: Wrong Answer

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[0][0] = 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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。

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)]
L = set([])
reach = set([])
reach.add((sx,sy))
def dfs(x,y,stp):
  if x==0 or x==H-1 or y==0 or y==W-1:
    print(1)
    exit()
  if Room[x][y] == "#":
    return
  if stp <= K:
    L.add((x,y))
    if stp == K:
      return
  stp +=1
  for i in range(4):
    nx = x+d[i][0]
    ny = y+d[i][1]
    if nx<0 or nx>=H or ny<0 or ny>= W or Room[nx][ny] == "#" or (nx,ny) in reach:
      continue
    reach.add((nx,ny))
    dfs(nx,ny,stp)

dfs(sx,sy,0)
INF = float("inf")
ans = INF

for t in L:
  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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。

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)]
L = set([])
reach = set([])
reach.add((sx,sy))
def dfs(x,y,stp):
  if x==0 or x==H-1 or y==0 or y==W-1:
    print(1)
    exit()
  if Room[x][y] == "#":
    return
  if stp <= K:
    L.add((x,y))
    if stp == K:
      return
  stp +=1
  for i in range(4):
    nx = x+d[i][0]
    ny = y+d[i][1]
    if nx<0 or nx>=H or ny<0 or ny>= W or Room[nx][ny] == "#" or (nx,ny) in reach:
      continue
    reach.add((nx,ny))
    dfs(nx,ny,stp)

dfs(sx,sy,0)
INF = float("inf")
ans = INF

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000) #これがないと再帰の回数オーバーでエラー出る。

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)]
L = set([])
reach = set([])
reach.add((sx,sy))
def dfs(x,y,stp):
  if x<0 or x>= H or y<0 or y>= W:
    print(1)
    exit()
  if Room[x][y] == "#":
    return
  if stp <= K:
    L.add((x,y))
    if stp == K:
      return
  stp +=1
  for i in range(4):
    nx = x+d[i][0]
    ny = y+d[i][1]
    if nx<0 or nx>=H or ny<0 or ny>= W or Room[nx][ny] == "#" or (nx,ny) in reach:
      continue
    reach.add((nx,ny))
    dfs(nx,ny,stp)

dfs(sx,sy,0)
INF = float("inf")
ans = INF

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

Submission status: Wrong Answer

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 // 2)


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

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:
        u = q.popleft()
        for x, y in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            vx, vy = (u[0]+x, u[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[u[0]][u[1]]
            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)
        error_print(x, y, H, W, t)

    return 1 + -(-ans // 2)


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

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 = []
    while q:
        u = q.popleft()
        for x, y in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            vx, vy = (u[0]+x, u[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[u[0]][u[1]]
            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)
        error_print(x, y, H, W, t)

    return 1 + -(-ans // 2)


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

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, 0)])
    d = {}
    d[s] = 0
    while q:
        u, c = q.popleft()
        for x, y in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            vx, vy = (u[0]+x, u[1]+y)
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] != '.':
                continue
            if c + 1 <= K:
                q.append(((vx, vy), c+1))
                d[(vx, vy)] = 0

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

    return 1 + -(-ans // 2)


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

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, 0)])
    d = {}
    d[s] = 0
    while q:
        u, c = q.popleft()
        for x, y in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            vx, vy = (u[0]+x, u[1]+y)
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] != '.':
                continue
            if c + 1 <= K:
                q.append(((vx, vy), c+1))
                d[(vx, vy)] = 0
    ans = INF
    for x, y in d.keys():
        t = min(abs(x), abs(x-H-1), abs(y), abs(y-W-1))
        ans = min(ans, t)

    return 1 + -(-ans // 2)


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

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, 0)])
    d = {}
    d[s] = 0
    while q:
        u, c = q.popleft()
        for x, y in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            vx, vy = (u[0]+x, u[1]+y)
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] != '.':
                continue
            if c + 1 <= K:
                q.append(((vx, vy), c+1))
                d[(vx, vy)] = 0
    q = set()
    for u in list(d.keys()):
        for x, y in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            vx, vy = (u[0]+x, u[1]+y)
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if (vx, vy) not in d:
                q.add(((vx, vy), 1))
                d[(vx, vy)] = 1
    q = deque(q)

    while q:
        u, c = q.popleft()
        for x, y in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            vx, vy = (u[0]+x, u[1]+y)
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if (vx, vy) not in d:
                q.append(((vx, vy), c+1))
                d[(vx, vy)] = c+1

    ans = INF
    for j in range(W):
        ans = min(ans, d[(0, j)])
        ans = min(ans, d[(H-1, j)])
    for i in range(H):
        ans = min(ans, d[(i, 0)])
        ans = min(ans, d[(i, W-1)])
    return -(-ans // 2) + 1



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

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    a = [input() for _ in range(h)]
    for i,ai in enumerate(a):
        if "S" in ai:
            si = i
            sj = ai.find("S")
            break
    q = queue.Queue()
    t = [[10**10]*w for _ in [0]*h]
    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    t[si][sj] = 0
    q.put((si,sj))
    g1 = [(si,sj)]
    while not q.empty():
        qi,qj = q.get()
        for di,dj in dir:
            if 0 <= qi+di <= h-1 and 0 <= qj+dj <= w-1 and a[qi+di][qj+dj] == ".":
                if t[qi+di][qj+dj] > t[qi][qj] + 1:
                    t[qi+di][qj+dj] = t[qi][qj] + 1
                    g1.append((qi+di,qj+dj))
                    if t[qi][qj] != k:
                        q.put((qi+di,qj+dj))
    mi = 10**4
    for i,j in g1:
        if mi > (i+k-1)//k+1:
            mi = (i+k-1)//k+1
        if mi > (j+k-1)//k+1:
            mi = (j+k-1)//k+1
        if mi > (h-1-i+k-1)//k+1:
            mi = (h-1-i+k-1)//k+1
        if mi > (w-1-j+k-1)//k+1:
            mi = (w-1-j+k-1)//k+1
    print(mi)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K,*L = open(0).read().split()
L = [list(a) for a in L]
H,W,K = map(int, (H,W,K))
q = deque([])
step = [(-1,0),(1,0),(0,-1),(0,1)]
for i,a in enumerate(L):
  if 'S' in a:
    q = deque([(0,i,a.index('S'))])
    break
ans = 10**10
while q:
  c,a,b = q.popleft()
  x = min(a,H-a-1,b,W-b-1)
  cnt = 1+(x+K-1)//K
  ans = min(cnt,ans)
  if c+1>K:
    continue
  for dx,dy in step:
    n = a+dx
    m = b+dy
    if not(-1<n<H and -1<m<W):
      continue
    if L[n][m]=='.':
      L[n][m]='#'
      q.append((n,m,c+1))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K,*L = open(0).read().split()
H,W,K = map(int, (H,W,K))
q = deque([])
step = [(-1,0),(1,0),(0,-1),(0,1)]
for i,a in enumerate(L):
  a = list(a)
  if 'S' in a:
    q = deque([(0,i,a.index('S'))])
    break
ans = 10**10
while q:
  c,a,b = q.popleft()
  x = min(a,H-a-1,b,W-b-1)
  cnt = 1+(x+K-1)//K
  ans = min(cnt,ans)
  if c+1>K:
    continue
  for dx,dy in step:
    n = a+dx
    m = b+dy
    if not(-1<n<H and -1<m<W):
      continue
    if L[n][m]=='.':
      L[n][m]=='#'
      q.append((n,m,c+1))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K,*L = open(0).read().split()
H,W,K = map(int, (H,W,K))
q = deque([])
step = [(-1,0),(1,0),(0,-1),(0,1)]
for i in range(H):
  flag = False
  for j in range(W):
    if L[i][j]=='S':
      q.append((i,j,0))
      flag = True
      break
  if flag:
    break
dist = [10**10 for i in range(H*W)]
ans = 10**10
while q:
  a,b,c = q.popleft()
  x = min(i,H-a-1,j,W-b-1)
  cnt = 1+(x+K-1)//K
  ans = min(cnt,ans)
  dist[a*W+b] = c
  if c+1>K:
    continue
  for dx,dy in step:
    n = a+dx
    m = b+dy
    if not(-1<n<H and -1<m<W):
      continue
    if dist[n*W+m]<c+1:
      continue
    if L[n][m]=='.':
      q.append((n,m,c+1))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W,K,*L = open(0).read().split()
H,W,K = map(int, (H,W,K))
q = deque([])
step = [(-1,0),(1,0),(0,-1),(0,1)]
for i in range(H):
  flag = False
  for j in range(W):
    if L[i][j]=='S':
      q.append((i,j,0))
      flag = True
      break
  if flag:
    break
dist = [[10**10]*W for i in range(H)]
dist[i][j] = 0
while q:
  a,b,c = q.popleft()
  dist[a][b] = c
  if c+1>K:
    continue
  for dx,dy in step:
    n = a+dx
    m = b+dy
    if not(-1<n<H and -1<m<W):
      continue
    if dist[n][m]<c+1:
      continue
    if L[n][m]=='.':
      q.append((n,m,c+1))
      
ans = 10**10
for i in range(H):
  for j in range(W):
    if dist[i][j]==-1:
      continue
    x = min(i,H-i-1,j,W-j-1)
    cnt = 1+(x+K-1)//K
    ans = min(cnt,ans)
print(ans)

Submission status: Wrong Answer

Solution code:

# AGC014C
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,k = map(int, input().split())
A = [None] * h
for i in range(h):
    A[i] = input()
    if  "S" in A[i]:
        start = (i, A[i].index("S"))

dx = [0,1,0,-1]
dy = [1,0,-1,0]
hp = [(0, start)] # (距離, ノード番号)
import heapq
from collections import defaultdict
seen = set()
near = set()
end = False
while hp:
    val, u = heapq.heappop(hp)
    if val<=k:
        near.add(u)
        if u[0]==0 or u[0]==h-1 or u[1]==0 or u[1]==w-1:
            print(1)
            end = True
            break
    else:
        break
    for i, j in zip(dx,dy):
        xx, yy = u[0]+i, u[1]+j
        if xx<0 or xx>=h or yy<0 or yy>=w:
            continue
        if A[xx][yy]=="#":
            continue
        if not (xx,yy) in seen:
            seen.add((xx,yy))
            heapq.heappush(hp, (val+1, (xx,yy)))
if not end:
    hp = list((0, u) for u in near)
    dist = {}
    for u in near:
        dist[u] = 0
    while hp:
        val, u = heapq.heappop(hp)
        if u[0]==0 or u[0]==h-1 or u[1]==0 or u[1]==w-1:
            print((val)//k + int((val)%k) + 1)
            break
        for i, j in zip(dx,dy):
            xx, yy = u[0]+i, u[1]+j
            if xx<0 or xx>=h or yy<0 or yy>=w:
                continue
            if not (xx,yy) in dist or dist[xx,yy]>val+1:
                heapq.heappush(hp, (val+1, (xx,yy)))
                dist[xx,yy] = val+1

Submission status: Wrong Answer

Solution code:

# AGC014C
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))
    write = lambda x: sys.stdout.write(x+"\n")


    h,w,k = map(int, input().split())
    A = [None] * h
    for i in range(h):
        A[i] = input()
        if  "S" in A[i]:
            start = (i, A[i].index("S"))

    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    hp = [(0, start)] # (距離, ノード番号)
    import heapq
    from collections import defaultdict
    seen = set()
    near = set()
    while hp:
        val, u = heapq.heappop(hp)
        if val<=k:
            near.add(u)
            if u[0]==0 or u[0]==h-1 or u[1]==0 or u[1]==w-1:
                print(1)
                return
        else:
            break
        for i, j in zip(dx,dy):
            xx, yy = u[0]+i, u[1]+j
            if xx<0 or xx>=h or yy<0 or yy>=w:
                continue
            if A[xx][yy]=="#":
                continue
            if not (xx,yy) in seen:
                seen.add((xx,yy))
                heapq.heappush(hp, (val+1, (xx,yy)))
    
    hp = list((0, u) for u in near)
    dist = {}
    while hp:
        val, u = heapq.heappop(hp)
        if u[0]==0 or u[0]==h-1 or u[1]==0 or u[1]==w-1:
            print((val)//k + int((val)%k) + 1)
            return
        for i, j in zip(dx,dy):
            xx, yy = u[0]+i, u[1]+j
            if xx<0 or xx>=h or yy<0 or yy>=w:
                continue
            if not (xx,yy) in dist or dist[xx,yy]>val+1:
                heapq.heappush(hp, (val+1, (xx,yy)))
                dist[xx,yy] = val+1

main()

Submission status: Wrong Answer

Solution code:

# AGC014C
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))
    write = lambda x: sys.stdout.write(x+"\n")


    h,w,k = map(int, input().split())
    A = [None] * h
    for i in range(h):
        A[i] = input()
        if  "S" in A[i]:
            start = (i, A[i].index("S"))

    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    hp = [(0, start)] # (距離, ノード番号)
    import heapq
    from collections import defaultdict
    seen = set()
    near = set()
    while hp:
        val, u = heapq.heappop(hp)
        if val<=k:
            near.add(u)
            if u[0]==0 or u[0]==h-1 or u[1]==0 or u[1]==w-1:
                print(1)
                return
        else:
            break
        for i, j in zip(dx,dy):
            xx, yy = u[0]+i, u[1]+j
            if xx<0 or xx>=h or yy<0 or yy>=w:
                continue
            if A[xx][yy]=="#":
                continue
            if not (xx,yy) in seen:
                seen.add((xx,yy))
                heapq.heappush(hp, (val+1, (xx,yy)))
    
    hp = list((0, u) for u in near)
    dist = {}
    while hp:
        val, u = heapq.heappop(hp)
        for i, j in zip(dx,dy):
            xx, yy = u[0]+i, u[1]+j
            if xx<0 or xx>=h or yy<0 or yy>=w:
                continue
            if not (xx,yy) in dist or dist[xx,yy]>val+1:
                heapq.heappush(hp, (val+1, (xx,yy)))
                dist[xx,yy] = val+1
                if xx==0 or xx==h-1 or yy==0 or yy==w-1:
                    print((val+1)//k + int((val+1)%k) + 1)
                    return

main()