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:

# 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()

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

    def sub():
        best = 10**10
        for i in range(h):
            for j in (0, w-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        for j in range(w):
            for i in (0, h-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        return best

    print(sub()+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)
    seen = set()
    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 seen:
                seen.add((xx,yy))
                heapq.heappush(hp, (val+1, (xx,yy)))
                if xx==0 or xx==h-1 or yy==0 or yy==w-1:
                    dist[xx,yy] = val+1

    def sub():
        best = 10**10
        for i in range(h):
            for j in (0, w-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        for j in range(w):
            for i in (0, h-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        return best

    print(sub()+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)
    seen = set()
    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 seen:
                seen.add((xx,yy))
                heapq.heappush(hp, (val+1, (xx,yy)))
                if xx==0 or xx==h-1 or yy==0 or yy==w-1:
                    dist[xx,yy] = val+1

    def sub(x):
        best = 10**10
        for i in range(h):
            for j in (0, w-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        for j in range(w):
            for i in (0, h-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        return best<=x

    l = 0
    r = 2000
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    print(r+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)
    seen = set()
    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 seen:
                seen.add((xx,yy))
                heapq.heappush(hp, (val+1, (xx,yy)))
                if xx==0 or xx==h-1 or yy==0 or yy==w-1:
                    dist[xx,yy] = val+1

    def sub(x):
        best = 10**10
        for i in range(h):
            for j in (0, w-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        for j in range(w):
            for i in (0, h-1):
                v = dist[i,j]//k + int(dist[i,j]%k)
                best = min(best, v)
        return best<=x

    l = 0
    r = 1000
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    print(r+1)
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p={(x,y)}
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    l[wx][wy]=1
    p.add((wx,wy))
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":

            p.add((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) ):
                global ans
                ans=1
dfs(x,y,0)

for g,j in p:
    if ans!=min(ans,-((-min(g,w-j-1,h-g-1,j))//k)+1):
        ans=(-((-min(g,w-j-1,h-g-1,j))//k)+1)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p=[(x,y)]
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":
            l[wx+a][wy+s]=1
            p.append((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) )and cnt<=k:
                global ans
                ans=1
                #print("!")
dfs(x,y,0)

for g,j in p:
    ans=min(ans,-((-min(g,w-j-1,h-g-1,j))//k)+1)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p=[(x,y)]
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":
            l[wx+a][wy+s]=1
            p.append((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) )and cnt<k:
                global ans
                ans=1
                #print("!")
dfs(x,y,0)

for g,j in p:
    ans=min(ans,-((-min(g,w-j-1,h-g-1,j))//k)+1)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p=[(x,y)]
def dfs(wx,wy,cnt):
    if cnt==k:return 1
    if l[wx][wy]:return 1
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":
            l[wx+a][wy+s]=1
            p.append((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) )and cnt<k:
                global ans
                ans=1
                #print("!")
dfs(x,y,0)

for g,j in p:
    ans=min(ans,-((-min(g,w-j-1,h-g-1,j))//k)+1)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p=[(x,y)]
def dfs(wx,wy,cnt):
    if cnt==k:return 1
    if l[wx][wy]:return 1
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":
            l[wx+a][wy+s]=1
            p.append((wx+a,s+wy))
            dfs(wx+a,wy+s,cnt+1)
            if (wx+a in (0,h-1)or wy+s in (0,w-1) )and cnt<k:
                global ans
                ans=1
                #print("!")
dfs(x,y,0)

for g,j in p:
    ans=min(ans,-((-min(g+1,w-j,h-g,j+1))//k)+1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = map(int,input().split())
A = []
ans = 10**10
for i in range(h):
    A.append(input())
    for j in range(w):
        if A[i][j] == 'S':
            start = (i,j)
d = [[10**10]*w for _ in range(h)]
d[start[0]][start[1]] = 0
que = deque([start])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
while que:
    px,py = que.popleft()
    ans = min(ans, 2 + (min(px,py,h-px-1,w-py-1)-1)//k)
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0 <= nx < w and 0 <= ny < h and A[nx][ny] == '.' and d[nx][ny] == 10**10:
            d[nx][ny] = d[px][py] + 1
            if d[nx][ny] <= k:
                que.append((nx,ny))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = map(int,input().split())
A = []
ans = 10**10
for i in range(h):
    A.append(input())
    for j in range(w):
        if A[-1][j] == 'S':
            start = (i,j)
d = [[10**10]*w for _ in range(h)]
d[start[0]][start[1]] = 0
que = deque([start])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
while que:
    px,py = que.popleft()
    ans = min(ans, 2 + (min(px,py,w-px-1,h-py-1)-1)//k)
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0 <= nx < w and 0 <= ny < h and A[nx][ny] == '.' and d[nx][ny] == 10**10:
            d[nx][ny] = d[px][py] + 1
            if d[nx][ny] <= k:
                que.append((nx,ny))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w,k = map(int,input().split())
A = []
ans = 10**10
for i in range(h):
    A.append(input())
    for j in range(w):
        if A[-1][j] == 'S':
            start = (i,j)
d = [[10**10]*w for _ in range(h)]
d[start[0]][start[1]] = 0
que = deque([start])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
while que:
    px,py = que.popleft()
    ans = min(ans, 2 + (min(px,py,w-px-1,h-py-1)-1)//k)
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0 <= nx < w and 0 <= ny < h and A[nx][ny] == '.':
            d[nx][ny] = d[px][py] + 1
            if d[nx][ny] <= k:
                que.append((nx,ny))
print(ans)

Submission status: Wrong Answer

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

h, w, k = map(int, input().split())
A = [input().rstrip() for _ in range(h)]
for i, a in enumerate(A):
  if "S" in a:
    sy = i
    sx = a.index("S")
    break

que = deque()
dist = [[-1]*w for _ in range(h)]
D = ((-1, 0), (0, -1), (1, 0), (0, 1))
        
def dfs(y, x):
  seen = [0]*h
  seen[y] |= 1 << x
  stack = [(y, x, 0)]
  while stack:
    ny, nx, cnt = stack.pop()
    dist[ny][nx] = k
    que.append((ny, nx))
    if cnt == k:
      continue
    for dy, dx in D:
      yy, xx = ny+dy, nx+dx
      if 0 <= yy < h and 0 <= xx < w:
        if A[yy][xx] == "#":
          continue
        if seen[yy] >> xx & 1:
          continue
        seen[yy] |= 1 << xx
        stack.append((yy, xx, cnt+1))

dfs(sy, sx)

while que:
  y, x = que.popleft()
  if y == 0 or y == h-1 or x == 0 or x == w-1:
    ans = -(-dist[y][x] // k)
    break
  for dy, dx in D:
    ny, nx = y+dy, x+dx
    if 0 <= ny < h and 0 <= nx < w:
      if dist[ny][nx] == -1:
        dist[ny][nx] = dist[y][x] + 1
        que.append((ny, nx))

print(ans)

Submission status: Wrong Answer

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

h, w, k = map(int, input().split())
A = [input().rstrip() for _ in range(h)]
for i, a in enumerate(A):
  if "S" in a:
    sy = i
    sx = a.index("S")
    break

que = deque()
dist = [[-1]*w for _ in range(h)]
D = ((-1, 0), (0, -1), (1, 0), (0, 1))
        
def dfs(y, x):
  seen = [0]*h
  stack = [(y, x, 0)]
  while stack:
    ny, nx, cnt = stack.pop()
    dist[ny][nx] = k
    que.append((ny, nx))
    if cnt == k:
      continue
    for dy, dx in D:
      yy, xx = ny+dy, nx+dx
      if 0 <= yy < h and 0 <= xx < w:
        if A[yy][xx] == "#":
          continue
        if seen[yy] >> xx & 1:
          continue
        seen[yy] |= 1 << xx
        stack.append((yy, xx, cnt+1))

dfs(sy, sx)

while que:
  y, x = que.popleft()
  if y == 0 or y == h-1 or x == 0 or x == w-1:
    ans = -(-dist[y][x] // k)
    break
  for dy, dx in D:
    ny, nx = y+dy, x+dx
    if 0 <= ny < h and 0 <= nx < w:
      if dist[ny][nx] == -1:
        dist[ny][nx] = dist[y][x] + 1
        que.append((ny, nx))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

#入力
h,w,k=map(int,input().split())
a=[input() for i in range(h)]

#Sの位置の捜索
for i in range(h):
    for j in range(w):
        if a[i][j]=='S':
            sy,sx=i,j

#各種パラメータの初期設定
d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
    dist.append([inf]*w)
dist[sy][sx]=0

#一回目の魔法で移動できる範囲を幅優先探索
while len(d)!=0:
    b=d.popleft()
    p,q=b[0],b[1]
    for i in [[1,0],[0,-1],[-1,0],[0,1]]:
        by,bx=b[0]+i[0],b[1]+i[1]
        if bx>=0 and bx<w and by>=0 and by<h and a[by][bx]!='#' and dist[by][bx]==-1 and dist[p][q]<k:
            #訪問先が配列内かつ壁でなく未訪問、訪問元の距離がk以下のとき訪問
            d.append([by,bx])
            dist[by][bx]=dist[p][q]+1

#一回目で移動できる各地点からの魔法の使用回数を計算
for i in range(h):
    for j in range(w):
        if dist[i][j]!=-1:
            m=min(m,0--min(i-1,j-1,h-i,w-j)//k)

print(m+1)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

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

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=[(s[0],s[1],0)]
while que:
    posx,posy,count=que.pop()
    if count==K:
        continue

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            que.append((nx,ny,count+1))

ans=float("inf")
while start:
    x,y=start.pop()
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

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

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=[(s[0],s[1],0)]
while que:
    posx,posy,count=que.pop()
    if count==K:
        break

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            que.append((nx,ny,count+1))

ans=float("inf")
while start:
    x,y=start.pop()
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
A=["" for i in range(H)]
for i in range(H):
    A[i]=input()

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

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=[(s[0],s[1],0)]
while que:
    posx,posy,count=que.pop()
    if count==K:
        break

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="#" and (nx,ny) not in start:
            start.add((nx,ny))
            que.append((nx,ny,count+1))

ans=float("inf")
while start:
    x,y=start.pop()
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
A=[input() for i in range(H)]
for i,l in enumerate(A):
    if 'S' in l:
        S=(K,i,l.index('S'))
from collections import deque
q=deque([S])
X=[(S[1],S[2])]
n=((0,1),(0,-1),(1,0),(-1,0))
v=[[0]*W for i in range(H)]
v[S[1]][S[2]]=1
while q:
    m,i,j=q.popleft()
    for x,y in n:
        if 0<=i+x<H and 0<=j+y<W:
            if v[i+x][j+y]:continue
            v[i+x][j+y]=1
            if A[i+x][j+y]=='.' and m>0:
                q.append((m-1,i+x,j+y))
                X.append((i+x,i+y))
print(min([min(0--i//K,0--(H-i-1)//K,0--j//K,0--(W-j-1)//K) for i,j in X])+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

#入力
h,w,k=map(int,input().split())
a=[input() for i in range(h)]

#Sの位置の捜索
for i in range(h):
    for j in range(w):
        if a[i][j]=='S':
            sy,sx=i,j

#各種パラメータの初期設定
d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
    dist.append([inf]*w)
dist[sy][sx]=0

#一回目の魔法で移動できる範囲を幅優先探索
while len(d)!=0:
    b=d.popleft()
    p,q=b[0],b[1]
    for i in [[1,0],[0,-1],[-1,0],[0,1]]:
        by,bx=b[0]+i[0],b[1]+i[1]
        if bx>=0 and bx<w and by>=0 and by<h and a[by][bx]!='#' and dist[by][bx]==-1 and dist[p][q]<k:
            #訪問先が配列内かつ壁でなく未訪問、訪問元の距離がk以下のとき訪問
            d.append([by,bx])
            dist[by][bx]=dist[p][q]+1

#一回目で移動できる各地点からの魔法の使用回数を計算
for i in range(h):
    for j in range(w):
        if dist[i][j]!=-1:
            m=min(m,math.ceil(i/k),math.ceil(h-i-1/k),math.ceil(j/k),math.ceil(w-j-1/k))

print(m+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

#入力
h,w,k=map(int,input().split())
a=[input() for i in range(h)]

#Sの位置の捜索
for i in range(h):
    for j in range(w):
        if a[i][j]=='S':
            sy,sx=i,j

#各種パラメータの初期設定
d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
    dist.append([inf]*w)
dist[sy][sx]=0

#一回目の魔法で移動できる範囲を幅優先探索
while len(d)!=0:
    b=d.popleft()
    p,q=b[0],b[1]
    for i in [[1,0],[0,-1],[-1,0],[0,1]]:
        by,bx=b[0]+i[0],b[1]+i[1]
        if bx>=0 and bx<w and by>=0 and by<h:
            if a[by][bx]!='#' and dist[by][bx]==-1 and dist[p][q]<k:
                #訪問先が配列内かつ壁でなく未訪問、訪問元の距離がk以下のとき訪問
                d.append([by,bx])
                dist[by][bx]=dist[p][q]+1

#一回目で移動できる各地点からの魔法の使用回数を計算
for i in range(h):
    for j in range(w):
        if dist[i][j]!=-1:
            m=min(m,math.ceil(i/k),math.ceil(h-i-1/k),math.ceil(j/k),math.ceil(w-j-1/k))

print(m+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

#入力
h,w,k=map(int,input().split())
a=[input() for i in range(h)]

#Sの位置の捜索
for i in range(h):
    for j in range(w):
        if a[i][j]=='S':
            sy,sx=i,j

#各種パラメータの初期設定
d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
    dist.append([inf]*w)
dist[sy][sx]=0

#一回目の魔法で移動できる範囲を幅優先探索
while len(d)!=0:
    b=d.popleft()
    p,q=b[0],b[1]
    for i in [[1,0],[0,-1],[-1,0],[0,1]]:
        by,bx=b[0]+i[0],b[1]+i[1]
        if bx>=0 and bx<w and by>=0 and by<h and a[by][bx]!='#' and dist[by][bx]==-1 and dist[p][q]<=k:
            #訪問先が配列内かつ壁でなく未訪問、訪問元の距離がk以下のとき訪問
            d.append([by,bx])
            dist[by][bx]=dist[p][q]+1

#一回目で移動できる各地点からの魔法の使用回数を計算
for i in range(h):
    for j in range(w):
        if dist[i][j]!=-1:
            m=min(m,math.ceil(i/k),math.ceil(w-i-1/k),math.ceil(j/k),math.ceil(w-j-1/k))

print(m+1)

Submission status: Wrong Answer

Solution code:
h, w, kk = [int(i) for i in input().split()]
mi = [[10 ** 18] * w for _ in range(h)]

a = []
q = []
for l in range(h):
    s = input()
    b = []
    for j, k in enumerate(s):
        b.append(k != "#")
        if k == "S":
            q.append([l, j, 0])
            mi[l][j] = 0
    a.append(b)

k = 0
while True:
    if k == len(q):
        break
    i, j, c = q[k]
    k += 1
    if c < kk:
        e = j
        for d in range(i - 1, 1 + 2, 2):
            if 0 <= d < h and 0 <= e < w and a[d][e]:
                    if mi[d][e] != 0:
                        mi[d][e] = 0
                        q.append([d, e, c + 1])
                        
                        if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                            print(1)
                            exit()
        d = i
        for e in range(j - 1, j + 2, 2):
            if 0 <= d < h and 0 <= e < w and a[d][e]:
                
                if mi[d][e] !=0:
                    mi[d][e] = 0
                    q.append([d, e, c + 1])
                    
                    if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                        print(1)
                        exit()
    else:
        break
for i in q:
    i[-1] = 0
k = 0
while True:
    i, j, c = q[k]
    k+=1
    e = j
    for d in range(i-1, 1+2, 2):
        if 0 <= d < h and 0 <= e < w:
            if mi[d][e] > c + 1:
                mi[d][e] = c + 1
                q.append([d, e, c + 1])
                
                if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                    print(c//kk+2)
                    exit()
    d = i
    for e in range(j-1, j+2, 2):
        if 0 <= d < h and 0 <= e < w:
            if mi[d][e] > c + 1:
                mi[d][e] = c + 1
                q.append([d, e, c + 1])
                
                if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                    print(c//kk+2)
                    exit()

Submission status: Wrong Answer

Solution code:
h, w, kk = [int(i) for i in input().split()]
mi = [[10 ** 18] * w for _ in range(h)]

a = []
q = []
for l in range(h):
    s = input()
    b = []
    for j, k in enumerate(s):
        b.append(k != "#")
        if k == "S":
            q.append([l, j, 0])
            mi[l][j] = 0
    a.append(b)

k = 0
while True:
    if k == len(q):
        break
    i, j, c = q[k]
    k += 1
    if c < kk:
        e = j
        for d in range(i - 1, 1 + 2, 2):
            if 0 <= d < h and 0 <= e < w and a[d][e]:
                    if mi[d][e] != kk:
                        mi[d][e] = kk
                        q.append([d, e, c + 1])
                        
                        if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                            print(1)
                            exit()
        d = i
        for e in range(j - 1, j + 2, 2):
            if 0 <= d < h and 0 <= e < w and a[d][e]:
                
                if mi[d][e] !=kk:
                    mi[d][e] = kk
                    q.append([d, e, c + 1])
                    
                    if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                        print(1)
                        exit()
    else:
        break

k = 0
while True:
    i, j, c = q[k]
    k+=1
    e = j
    for d in range(i-1, 1+2, 2):
        if 0 <= d < h and 0 <= e < w:
            if mi[d][e] > c + 1:
                mi[d][e] = c + 1
                q.append([d, e, c + 1])
                
                if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                    print(c//kk+1)
                    exit()
    d = i
    for e in range(j-1, j+2, 2):
        if 0 <= d < h and 0 <= e < w:
            if mi[d][e] > c + 1:
                mi[d][e] = c + 1
                q.append([d, e, c + 1])
                
                if d == 0 or d == h - 1 or e == 0 or e == w - 1:
                    print(c//kk+1)
                    exit()