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 copy
H,W,K=map(int,input().split())
A=[]
S=[]
for i in range(H):
    a=list(input())
    for j in range(W):
        if a[j]=="S":
            S=[i,j]
            a[j]="."
    A.append(a)
#print(S)    
B=copy.deepcopy(A)
#print(B)
for i in range(H):
    for j in range(W):
        if (abs(S[0]-i)+abs(S[1]-j))<=K and B[i][j]==".":
            B[i][j]=10**10
        else:
            B[i][j]=2*10**15
#print(B)
P=[i for i in range(H*W)]
size=[1 for i in range(H*W)]

def find(x):
    if x==P[x]:
        return x
    else:
        return find(P[x])

def union(y,z):
    Y=find(y)
    Z=find(z)
    if size[Y]>=size[Z]:
        P[Z]=P[Y]
        size[Y]+=size[Z]
    else:
        P[Y]=P[Z]
        size[Z]+=size[Y]
        
for i in range(H):
    for j in range(W):
        if B[i][j]==10**10:
            if i-1>=0:
                if B[i-1][j]==10**10:
                    if find(i*W+j)!=find((i-1)*W+j):
                        union(i*W+j,(i-1)*W-j)
            if i+1<=(H-1):
                if B[i+1][j]==10**10:
                    if find(i*W+j)!=find((i+1)*W+j):
                        union(i*W+j,(i+1)*W+j)
            if j-1>=0:
                if B[i][j-1]==10**10:
                    if find(i*W+j)!=find((i)*W+(j-1)):
                        union(i*W+j,(i)*W+(j-1))
            if j+1<=0:
                if B[i][j+1]==10**10:
                    if find(i*W+j)!=find((i)*W+(j+1)):
                        union(i*W+j,(i)*W+(j+1))
            
p=P[S[0]*W+S[1]]
#print(p)
#print(P)
ANS=[10**5]
for i in range(H):
    for j in range(W):
        if P[i*W+j]==p:
            ANS.append(min(i,j,(H-1-i),(W-1-j)))
ans=min(ANS)
#print(ans)
if ans%K==0:
    print(ans//K+1)
else:
    print(ans//K+2)

Submission status: Wrong Answer

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)
            print(an,i,j)
            if ans>an:ans=an
print(-(-ans//k)+1)

Submission status: Wrong Answer

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
    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
            q.add((nx,ny))
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: Wrong Answer

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
    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
            q.add((nx,ny))
ans=10**9
for i in range(h):
    for j in range(w):
        if p[i][j]>=0:
            an=min(i,j,w-i-1,h-j-1)
            if ans>an:ans=an
print(-(-ans//k)+1)

Submission status: Wrong Answer

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
    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
            q.add((nx,ny))
ans=10**9
for i in range(h):
    for j in range(w):
        if p[i][j]>=0:
            ans=min(ans,i,j,h-i,w-j)
print(-(-ans//k)+1)

Submission status: Wrong Answer

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
    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
            q.add((nx,ny))
ans=10**9
for i in range(h):
    for j in range(w):
        if p[i][j]>=0:
            ans=min(ans,i,j,w-i,h-j)
print(-(-ans//k)+1)

Submission status: Wrong Answer

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:
  y,x,m=stack.popleft()
  if m>K:
    break
  a=min(a,min(x,W-1-x,y,H-1-y))
  if a==0:
    break
  for s1 in t:
    for s2 in t:
      if not visited[y+s1][x+s2] and grid[y+s1][x+s2]!="#":
        stack.append((y+s1,x+s2,m+1))
        visited[y+s1][x+s2]=True
ans=1+ceil(a/K)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
from math import ceil
H,W,K=map(int,input().split())
grid=[input() for i in range(H)]
G=defaultdict(set)
                               
for i in range(H):
  for j in range(W):
    if grid[i][j]=="S":
      S=(i,j)
    if grid[i][j]!="#":
      if i>0:
        if grid[i-1][j]!="#":
          G[(i,j)].add((i-1,j))
      if i<H-1:
        if grid[i+1][j]!="#":
          G[(i,j)].add((i+1,j))
      if j>0:
        if grid[i][j-1]!="#":
          G[(i,j)].add((i,j-1))
      if j<W-1:
        if grid[i][j+1]!="#":
          G[(i,j)].add((i,j+1))

stack=deque([(S[0],S[1],0)])
visited=[[False]*(W) for i in range(H)]
visited[S[0]][S[1]]=True
a=float("inf")
while stack:
  x,y,m=stack.popleft()
  if m>K:
    break
  a=min(a,min(x,W-1-x,y,H-1-y))
  for k in G[(x,y)]:
    if not visited[k[0]][k[1]]:
      stack.append((k[0],k[1],m+1))
      visited[k[0]][k[1]]=True
ans=1+ceil(a/K)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
from math import ceil
H,W,K=map(int,input().split())
grid=[input() for i in range(H)]
G=defaultdict(set)
                               
for i in range(H):
  for j in range(W):
    if grid[i][j]=="S":
      S=(i,j)
    if grid[i][j]!="#":
      if i>0:
        if grid[i-1][j]!="#":
          G[(i,j)].add((i-1,j))
      if i<H-1:
        if grid[i+1][j]!="#":
          G[(i,j)].add((i+1,j))
      if j>0:
        if grid[i][j-1]!="#":
          G[(i,j)].add((i,j-1))
      if j<W-1:
        if grid[i][j+1]!="#":
          G[(i,j)].add((i,j+1))

stack=deque([(S[0],S[1],0)])
visited=[[False]*(W) for i in range(H)]
visited[S[0]][S[1]]=True
a=float("inf")
while stack:
  x,y,m=stack.popleft()
  if m>K:
    break
  a=min(a,min(x,W+1-x,y,H+1-y))
  for k in G[(x,y)]:
    if not visited[k[0]][k[1]]:
      stack.append((k[0],k[1],m+1))
      visited[k[0]][k[1]]=True
ans=1+ceil(a/K)
print(ans)

Submission status: Wrong Answer

Solution code:
# https://beta.atcoder.jp/contests/agc014/submissions/1268295
import sys

input = sys.stdin.readline().rstrip


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]
    visited = [[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

    q = [(sy, sx, 0)]
    t = max(W, H)
    n = 1
    i = 0
    while n > 0:
        r, c, k = q[i]
        n -= 1
        visited[r][c] = True

        t = min(t, r, H - 1 - r, c, W - 1 - c)

        if t == 0:
            print(1)
            return

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

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from math import ceil
import sys

sys.setrecursionlimit(10 ** 9)


def start_pos():
    for r in range(H):
        for c in range(W):
            if a[r][c] == 'S':
                return r, c
    return -1, -1


def shortest_len(y, x):
    return min(y, H - 1 - y, x, W - 1 - x)


def dfs(y, x, k):
    global need_len
    if not (0 <= y < H and 0 <= x < W): return
    if a[y][x] == '#': return
    if b[y][x]: return
    b[y][x] = True
    sl = shortest_len(y, x)
    need_len = min(need_len, sl)
    if sl - (K - k) >= need_len: return
    if k == K: return
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        dfs(y + dy, x + dx, k + 1)


H, W, K = map(int, input().split())
a = [input() for _ in range(H)]
b = [[False for _ in range(W)] for _ in range(H)]
sy, sx = start_pos()
need_len = shortest_len(sy, sx)
dfs(sy, sx, 0)

print(1 + ceil(need_len / K))

'''
最初の魔法で、K回移動で到達できる範囲で、最も壁に近い場所まで移動する
以後、魔法を使用する毎に壁までの最短距離をKずつ移動する
壁に到達したら終了
'''

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)


def start_pos():
    for r in range(H):
        for c in range(W):
            if a[r][c] == 'S':
                return r, c
    return -1, -1


def shortest_len(y, x):
    return min(y, H - 1 - y, x, W - 1 - x)


def dfs(y, x, k):
    global need_len
    if not (0 <= y < H and 0 <= x < W): return
    if a[y][x] == '#': return
    if b[y][x]: return
    b[y][x] = True
    need_len = min(need_len, shortest_len(y, x))
    if k == 0: return
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        dfs(y + dy, x + dx, k - 1)


H, W, K = map(int, input().split())
a = [input() for _ in range(H)]
b = [[False for _ in range(W)] for _ in range(H)]
sy, sx = start_pos()
need_len = shortest_len(sy, sx)
dfs(sy, sx, K)

print(1 + (need_len + K - 1) // K)

'''
最初の魔法で、K回移動で到達できる範囲で、最も壁に近い場所まで移動する
以後、魔法を使用する毎に壁までの最短距離をKずつ移動する
壁に到達したら終了
'''

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000000)
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]== ".":
    dfs(x-1,y,z+1)
  if y > 0 and a[x][y-1]== ".":
    dfs(x,y-1,z+1)
  if x <h-1 and a[x+1][y]==".":
    dfs(x+1,y,z+1)
  if y <w-1 and a[x][y+1]==".":
    dfs(x,y+1,z+1)
dfs(sx,sy,0)
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: Wrong Answer

Solution code:
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
ty = tx = 0
while queue:
    y, x = queue.popleft()
    tr = min(y, x, h-1-y, w-1-x)
    if tr < r:
        r = tr
        ty, tx = y, x
    for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
        new_y, new_x = y+j, x+k
        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 -(-min(ty, tx, h-1-ty, w-1-tx) // K))

Submission status: Wrong Answer

Solution code:
h, w, k=map(int, raw_input().split())
a=["#"*(w+2)]+["#"+raw_input()+"#" for i in range(h)]+["#"*(w+2)]
q=[]
first=0
dis=[[0]*(w+2) for i in range(h+2)]
for i in range(h+2):
	for j in range(w+2):
		if a[i][j]=="S":
			q.append((i, j))
			dis[i][j]=1
while first<len(q):
	cur_x, cur_y=q[first]
	first+=1
	for next_x, next_y in ((cur_x+1, cur_y), (cur_x-1, cur_y), (cur_x, cur_y+1), (cur_x+1, cur_y-1)):
		if a[next_x][next_y]=="." and not dis[next_x][next_y]:
			q.append((next_x, next_y))
			dis[next_x][next_y]=dis[cur_x][cur_y]+1
result=h*w
for i in range(h+2):
	for j in range(w+2):
		if 0<dis[i][j]<=k+1:
			dis_exit=min(i-1, j-1, h-i, w-j)
			cnt=(dis_exit+k-1)/k
			result=min(result, 1+cnt)
print result

Submission status: Wrong Answer

Solution code:

from math import ceil
H, W, K = map(int, input().split())
 
A = [None] * H
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = (i, j)
                A[i] = A[i].replace('S', '.')
 
def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1
 
visited = [[False]*W for _ in range(H)]
visited[S[0]][S[1]]=True
next = [S]
for _ in range(K):
    next_t = []
    for p in next:
        x, y = p
        if is_edge(x, y):
            visited[x][y]=True
            continue
        if A[x - 1][y] == '.':
            if not visited[x-1][y]:
                next_t.append((x - 1, y))
        if A[x + 1][y] == '.':
            if not visited[x+1][y]:
                next_t.append((x + 1, y))
        if A[x][y - 1] == '.':
            if not visited[x][y-1]:
                next_t.append((x, y-1))
        if A[x][y + 1] == '.':
            if not visited[x][y+1]:
                next_t.append((x, y+1))
    next = next_t
 
 
def get_dist(x, y):
    return min(x, y, H - x - 1, W - y - 1)
 
min_dist = get_dist(*S)
for x in range(H):
    for y in range(W):
        if visited[x][y]:
            min_dist = min(min_dist, get_dist(*p))
 
print(ceil(min_dist / K) + 1)

Submission status: Wrong Answer

Solution code:
import sys

class Maze:
    def __init__ (self, H, W, K):
        self.info = {}
        self.info['H'] = H
        self.info['W'] = W
        self.info['K'] = K
        self.maze = []
    def makeMaze(self, Input):
        for i in xrange(self.info['H']):
            line = Input.readline().strip()
            self.maze.append(line)
            Taka = line.find('S')
            if Taka != -1:
                self.Taka = (i, Taka)
    def astar_in_k(self):
        def f(pos):
            k, h = table[pos[0]][pos[1]]
            return h-k
        def valid(pos):
            ret = True                                                                                                                                                                                                                
            ret &= (pos[0] >=0) and (pos[1] >= 0) and (pos[0] < H) and (pos[1]
            < W)
            ret &= not (table.get(pos[0], None) and table[pos[0]].get(pos[1],
            None) )
            if ret:
                ret &= self.maze[pos[0]][pos[1]] == '.'
            return ret
        def update(pos, value):
            table[pos[0]] = table.get(pos[0],{})
            table[pos[0]][pos[1]] = table[pos[0]].get(pos[1],value)
        table = {}
        table[self.Taka[0]] =\
        {self.Taka[1]:(self.info['K'],self.heu(self.Taka) )}
            ## self.heu will return heuristic value to the walls
        route = [self.Taka]
        best = self.Taka
        bestf = self.heu(self.Taka)
        while (route):
            r = route.pop(0)
            k, _ = table[r[0]][r[1]]
            if k == 0:
                break
            # scan for four directions d0~d1
            d = [
            (r[0]-1, r[1]),
            (r[0], r[1]+1),
            (r[0]+1, r[1]),
            (r[0], r[1]-1),
            ]
            for dd in d:
                if valid(dd):
                    update(dd, (k-1, self.heu(dd)))
                    if f(dd) < bestf:
                        best = dd
                        bestf = self.heu(dd)
                        if bestf == 0 or bestf == f(self.Taka) - K:
                            return best, bestf
                            
                        #if bestf == 0 or bestf == f(self.Taka) - K:
                        #    return best, bestf
                    route.append(dd)
            route = sorted(route, key = lambda x: f(x))
        return best, bestf
    def heu(self, pos):
        return min(pos[0], self.info['H']-pos[0], pos[1],
        self.info['W']-pos[1])

    
H,W,K = map(int, sys.stdin.readline().strip().split())
maze = Maze(H,W,K)
maze.makeMaze(sys.stdin)
_, heu = maze.astar_in_k()   
# for first round choose the path that will minimize the manhatan distance of
# Takahashi
print 1+ heu/K + bool(heu%K)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W, K = map(int, input().split())
m = [input() for i in range(H)]
v = [[0]*W for i in range(H)]
f = 0
for i in range(H):
	if f:
		break
	for j in range(W):
		if m[i][j] == "S":
			x = i
			y = j
			f = 1
			break
dq = deque([[x,y,0]])
v[x][y] = 1
ans = (min(x, y, H-1-x, W-1-y)+K-1)//K
while dq:
	x, y, c = dq.popleft()
	v[x][y] = 1
	ans = (min(x, y, H-1-x, W-1-y)+K-1)//K
	if c < K:
		c += 1
		if x > 0 and m[x-1][y] == "." and not v[x-1][y]:
			dq.append([x-1,y,c])
		if x < H-1 and m[x+1][y] == "." and not v[x+1][y]:
			dq.append([x+1,y,c])
		if y > 0 and m[x][y-1] == "." and not v[x][y-1]:
			dq.append([x,y-1,c])
		if y < W-1 and m[x][y+1] == "." and not v[x][y+1]:
			dq.append([x,y+1,c])
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W, K = map(int, raw_input().split())

MAP = [raw_input() for _ in xrange(H)]
visited = [[False for _ in xrange(W)] for _ in xrange(H)]

for i in range(H):
    x = MAP[i].find('S')
    if x != -1:
        sy = i
        sx = MAP[i].find('S')

Q = deque()
Q.append((0, (sx, sy)))
while len(Q) > 0:
    cost, [x, y] = Q.popleft()
    visited[y][x] = True
    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        px, py = x+dx, y+dy
        if px < 0 or px >= W:
            continue
        if py < 0 or py >= H:
            continue
        if visited[py][px]:
            continue
        if MAP[py][px] == "#":
            continue
        if cost + 1 < K:
            Q.append((cost + 1, (px, py)))

d = 10000
for x in xrange(W):
    for y in xrange(H):
        if visited[y][x]:
            d = min(d, x, W-1-x)
            d = min(d, y, H-1-y)

if d == 0:
    print 1
elif d < K:
    print 2
else:
    print 1 + d/K

Submission status: Wrong Answer

Solution code:
wall = "#"
space = "."

h, w, k = map(int, input().split())

ats = []
def search(ypos, xpos, depth):
    que = [[ypos, xpos, depth]]
    while que:
        ypos, xpos, depth = que.pop()
        if depth <= k:
            if (0 <= ypos < h - 1) and (0 <= xpos < w - 1) and cfield[ypos][xpos] == "." or cfield[ypos][xpos] == "S":
                cfield[ypos][xpos] = "N"
                que.append([ypos + 1, xpos, depth + 1])
                que.append([ypos - 1, xpos, depth + 1])
                que.append([ypos, xpos + 1, depth + 1])
                que.append([ypos, xpos - 1, depth + 1])
                at = min(
                        abs(0 - ypos),
                        abs(0 - xpos),
                        abs(h - 1 - ypos),
                        abs(w - 1 - xpos),
                        )
                ats.append(at)
    # print(1)
    # __import__("sys").exit()


field = []
cfield = []
for i in range(h):
    line = input()
    if "S" in line:
        spos = [i, line.index("S")]
    field.append(line)
    cfield.append(list(line))

search(spos[0], spos[1], 0)
# print(spos)
# for i in cfield:
#     print("".join(i))
#
# print(ats)
print((min(ats) + (k - 1)) // k + 1)

Submission status: Wrong Answer

Solution code:
from math import ceil
H, W, K = map(int, input().split())
 
A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')
 
def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

visited = [(S[0], S[1])]
l = 0
for i in range(K):
    for p in range(l, len(visited)):
        x, y = visited[p]
        if is_edge(x, y):
            continue
        if A[x - 1][y] == '.':
            visited.append((x - 1, y))
            l += 1
        if A[x + 1][y] == '.':
            visited.append((x + 1, y))
            l += 1
        if A[x][y - 1] == '.':
            visited.append((x, y - 1))
            l += 1
        if A[x][y + 1] == '.':
            visited.append((x, y + 1))
            l += 1
        
    

 
def get_dist(x, y):
    return min(x, y, H - x - 1, W - y - 1)
 
min_dist = get_dist(S[0], S[1])
for p in visited:
    min_dist = min(min_dist, get_dist(p[0], p[1]))
 
print(ceil(min_dist / K) + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W, K = map(int, input().split())
m = [input() for i in range(H)]
v = [[0]*W for i in range(H)]
f = 0
for i in range(H):
	if f:
		break
	for j in range(W):
		if m[i][j] == "S":
			x = i
			y = j
			f = 1
			break
stack = deque([[x,y,0]])
v[x][y] = 1
ans = (min(x, y, H-x, W-y)+K-1)//K
while stack:
	x, y, c = stack.popleft()
	v[x][y] = 1
	ans = (min(x, y, H-x, W-y)+K-1)//K
	if c < K:
		c += 1
		if x > 0 and m[x-1][y] == "." and not v[x-1][y]:
			stack.append([x-1,y,c])
		if x < H-1 and m[x+1][y] == "." and not v[x][y-1]:
			stack.append([x+1,y,c])
		if y > 0 and m[x][y-1] == "." and not v[x+1][y]:
			stack.append([x,y-1,c])
		if y < W-1 and m[x][y+1] == "." and not v[x][y+1]:
			stack.append([x,y+1,c])
print(ans+1)

Submission status: Wrong Answer

Solution code:
wall = "#"
space = "."

h, w, k = map(int, input().split())

ats = []
def search(ypos, xpos, depth):
    que = [[ypos, xpos, depth]]
    while que:
        ypos, xpos, depth = que.pop()
        if depth < k:
            if (0 <= ypos < h - 1) and (0 <= xpos < w - 1) and cfield[ypos][xpos] == "." or cfield[ypos][xpos] == "S":
                cfield[ypos][xpos] = "N"
                que.append([ypos + 1, xpos, depth + 1])
                que.append([ypos - 1, xpos, depth + 1])
                que.append([ypos, xpos + 1, depth + 1])
                que.append([ypos, xpos - 1, depth + 1])
                at = min(
                        abs(0 - ypos),
                        abs(0 - xpos),
                        abs(h - 1 - ypos),
                        abs(w - 1 - xpos),
                        )
                ats.append(at)
    # print(1)
    # __import__("sys").exit()


field = []
cfield = []
for i in range(h):
    line = input()
    if "S" in line:
        spos = [i, line.index("S")]
    field.append(line)
    cfield.append(list(line))

search(spos[0], spos[1], 0)
# print(spos)
# for i in cfield:
#     print("".join(i))
#
# print(ats)
print((min(ats) + (k - 1)) // k + 1)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
O = '_'
A = [O + input() + O for _ in range(H)]
A.insert(H, O * (W + 2))
A.insert(0, O * (W + 2))

# for a in A:
    # print(a)

sta = None
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if (A[i][j] == 'S'):
            sta = (i, j)
            break


def __mahou(sta, vec, B):
    mahou = 0
    pi, pj = sta
    A = B[:]
    goal = False
    while not goal:
        mahou += 1
        vi, vj = vec
        k = K
        while k > 0 and A[pi + vi][pj + vj] != '#':
            pi, pj = pi + vi, pj + vj
            goal = pi == 1 or pi == H or pj == 1 or pj == W
            if goal:
                break
            k -= 1
        if goal:
            break
        k = K
        ri, rj = pi + vi, pj + vj
        while k > 0 and not(ri == 0 or ri == H + 1 or rj == 0 or rj == W + 1):
            if A[ri][rj] == '#':
                A[ri] = A[ri][:rj] + '.' + A[ri][rj + 1:]
                k -= 1
            ri, rj = ri + vi, rj + vj
    return mahou

ans = 10000000
ans = min(ans, __mahou(sta, (-1, 0), A))
ans = min(ans, __mahou(sta, (1, 0), A))
ans = min(ans, __mahou(sta, (0, -1), A))
ans = min(ans, __mahou(sta, (0, 1), A))
print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = list(map(int, input().split()))
MAP = []
for i in range(H):
	MAP.append(list(input()))
for i in range(H):
	for j in range(W):
		if MAP[i][j] == "S":
			h = i
			w = j
			MAP[i][j] = "."
			break
		else:
			pass
length = min([h, w, H - h - 1, W - w - 1])
abl = [[h, w]]
for j in range(K):
	ln = len(abl)
	abll = []
	for i in range(ln):
		if MAP[abl[i][0] + 1][abl[i][1]] == ".":
			if abl[i][0] + 1 == H - 1:
				length = 0
				break
				break
			else:
				if H - abl[i][0] - 2 < length:
					length = H - abl[i][0] - 2
				else:
					pass
				abll.append([abl[i][0] + 1, abl[i][1]])
				MAP[abl[i][0] + 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0] - 1][abl[i][1]] == ".":
			if abl[i][0] - 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][0] - 1 < length:
					length = abl[i][0] - 1
				else:
					pass
				abll.append([abl[i][0] - 1, abl[i][1]])
				MAP[abl[i][0] - 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0]][abl[i][1] + 1] == ".":
			if abl[i][1] + 1 == W - 1:
				length = 0
				break
				break
			else:
				if W - abl[i][1] - 2 < length:
					length = W - abl[i][1] - 2
				else:
					pass
				abll.append([abl[i][0], abl[i][1] + 1])
				MAP[abl[i][0]][abl[i][1] + 1] = ","

		if MAP[abl[i][0]][abl[i][1] - 1] == ".":
			if abl[i][1] + 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][1] - 1 < length:
					length = abl[i][1] - 1
				else:
					pass
				abll.append([abl[i][0], abl[i][1] - 1])
				MAP[abl[i][0]][abl[i][1] - 1] = ","

if length % K == 0:
	print(int(length // K) + 1)
else:
	print(int(length // K) + 2)

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W, K = map(int, input().split())
m = [input() for i in range(H)]
v = [[0]*W for i in range(H)]
f = 0
for i in range(H):
	if f:
		break
	for j in range(W):
		if m[i][j] == "S":
			x = i
			y = j
			f = 1
			break
stack = deque([[x,y,0]])
v[x][y] = 1
ans = (min(x+1, y+1, H-x-1, W-y-1)+K-1)//K
while stack:
	x, y, c = stack.popleft()
	v[x][y] = 1
	ans = (min(x+1, y+1, H-x-1, W-y-1)+K-1)//K
	if c < K:
		c += 1
		if x > 0 and m[x-1][y] == "." and not v[x-1][y]:
			stack.append([x-1,y,c])
		if x < H-1 and m[x+1][y] == "." and not v[x][y-1]:
			stack.append([x+1,y,c])
		if y > 0 and m[x][y-1] == "." and not v[x+1][y]:
			stack.append([x,y-1,c])
		if y < W-1 and m[x][y+1] == "." and not v[x][y+1]:
			stack.append([x,y+1,c])
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
H,W,K = map(int,input().split())
HW = [list(input()) for i in range(H)]
for i,h in enumerate(HW):
	if "S" in h:
		y = i
		x = h.index("S")
A = [(x,y)]
m = 800
def idou(a,b):
	X = []
	for i2 in range(4):
		if i2 == 0:
			t,k = a - 1, b
		elif i2 == 1:
			t,k = a, b - 1
		elif i2 == 2:
			t,k = a + 1, b
		elif i2 == 3:
			t,k = a, b + 1
		if 0 <= t < W and 0 <= k < H and HW[k][t] == ".":
			HW[k][t] = "o"
			X.append((t,k))
	return X
cnt = 0
for p in A:
	cnt += 1
	x,y = p
	b = idou(x,y)
	A.extend(b)
	if cnt >= K:
		break
M = []
for i,w in enumerate(zip(*HW)):
	#print(w)
	if "o" in w or "S" in w:
		M.append(min(i,W - i - 1))
		
for i,h in enumerate(HW):
	if "S" in h or "o" in h:
		M.append(min(i, H - i - 1))
		#print(h)
m = min(M)
print(math.floor(m / K) + 1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

dx = (1, 0, -1, 0,)
dy = (0, 1, 0, -1,)

inf = 1<<60

def solve():
    def dfs(i, j, a, visited):
        visited[i][j] = True

        for l in range(len(dx)):
            ni = i + dy[l]
            nj = j + dx[l]

            if 0 <= ni < h and 0 <= nj < w:
                if (not visited[ni][nj]) and a[ni][nj]:
                    dfs(ni, nj, a, visited)

    h, w, k = map(int, sys.stdin.readline().split())

    si = -1
    sj = -1

    a = []

    for i in range(h):
        s = sys.stdin.readline().rstrip()
        a.append([ch != '#' for ch in s])

        if 'S' in s:
            si = i
            sj = s.find('S')

    # print(a)
    # print(si, sj)

    visited = [[False]*w for i in range(h)]

    dfs(si, sj, a, visited)

    # print(visited)

    ans = inf

    for i in range(h):
        for j in range(w):
            if visited[i][j]:
                tmp = min([h - 1 - i, i, w - 1 - j, j])
                tmp = (tmp + k - 1) // k + 1
                ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    solve()