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:
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[:]

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

ans = 1000000
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 = 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((m + K - 1) // K + 1)

Submission status: Wrong Answer

Solution code:
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((m + K - 1) // K)

Submission status: Wrong Answer

Solution code:
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((m + K - 1) // 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]])
ans = (min(x, y, H-x, W-y)+K-1)//K
while stack:
	x, y, c = stack.popleft()
	v[x][y] = 1
	if c < K:
		c += 1
		if x > 0 and m[x-1][y] == "." and not v[x-1][y]:
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x-1,y,c])
		if x < H-1 and m[x+1][y] == "." and not v[x][y-1]:
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x+1,y,c])
		if y > 0 and m[x][y-1] == "." and not v[x+1][y]:
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x,y-1,c])
		if y < W-1 and m[x][y+1] == "." and not v[x][y+1]:
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x,y+1,c])
print(ans+1)

Submission status: Wrong Answer

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

import sys
import os
import math

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
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
for p in A:
	x,y = p
	b = idou(x,y)
	A.extend(b)
M = []
for i,w in enumerate(zip(HW)):
	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))
m = min(M)
print((m + K - 1) // K + 1)

Submission status: Wrong Answer

Solution code:
#! -*- coding:utf-8 -*-
h,w,k = map(int,input().split())
a = []
for i in range(h):
    a.append(list(input()))

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j
            break

if si == 0 or sj == 0 or si == h-1 or sj == w-1:
    print(0)
elif (si - 1 == 0 and a[si-1][sj] == '.') or (sj - 1 == 0 and a[si][sj-1] == '.') or (si + 1 == h-1 and a[si+1][sj] == '.') or (sj + 1 == w-1 and a[si][sj+1] == '.'):
    print(1)
else:
    u,d,l,r = [],[],[],[]
    for i in range(h):
        if a[i][sj] == '#':
            if i <= si:
                u.append('#')
            else:
                d.append('#')
        else:
            if i <= si:
                u.append('.')
            else:
                d.append('.')
        
    for j in range(w):
        if a[si][j] == '#':
            if j <= sj:
                l.append('#')
            else:
                r.append('#')
        else:
            if j <= sj:
                l.append('.')
            else:
                r.append('.')
    u.pop()
    u.reverse()
    l.pop()
    l.reverse()
    
    #print(u,l,d,r)
    
    vu = 0
    while True:
        if u == []:
            break
        q = 0
        for i in range(k):
            try:
                if u[i-q] == '.':
                    u.pop(0)
                    q += 1
                else:
                    break
            except:
                pass
        count = 0
        for i in range(len(u)):
            if u[i] == '#':
                u[i] = '.'
                count += 1
            if count == k:
                break
        vu += 1

    vl = 0
    while True:
        if l == []:
            break
        q = 0
        for i in range(k):
            try:
                if l[i-q] == '.':
                    l.pop(0)
                    q += 1
                else:
                    break
            except:
                pass
        count = 0
        for i in range(len(l)):
            if l[i] == '#':
                l[i] = '.'
                count += 1
            if count == k:
                break
        vl += 1
        
    vd = 0
    while True:
        if d == []:
            break
        q = 0
        for i in range(k):
            try:
                if d[i-q] == '.':
                    d.pop(0)
                    q += 1
                else:
                    break
            except:
                pass
        count = 0
        for i in range(len(d)):
            if d[i] == '#':
                d[i] = '.'
                count += 1
            if count == k:
                break
        vd += 1        

    vr = 0
    while True:
        #print('---')
        #print(r)
        if r == []:
            break
        q = 0
        for i in range(k):
            try:
                if r[i-q] == '.':
                    r.pop(0)
                    q += 1
                else:
                    break
            except:
                pass
        count = 0
        #print(r)
        for i in range(len(r)):
            if r[i] == '#':
                r[i] = '.'
                count += 1
            if count == k:
                break
        vr += 1
        #print(r)

        
        
    #print(vu,vl,vd,vr)

    print(min(vu,vl,vd,vr))

Submission status: Wrong Answer

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

import sys
import os
import math

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

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

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

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
m = [input() 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 = [[x,y,0]]
ans = (min(x, y, H-x, W-y)+K-1)//K
while stack:
	x, y, c = stack.pop()
	if c < K:
		c += 1
		if x > 0 and m[x-1][y] == ".":
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x-1,y,c])
		if x < H-1 and m[x+1][y] == ".":
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x+1,y,c])
		if y > 0 and m[x][y-1] == ".":
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x,y-1,c])
		if y < W-1 and m[x][y+1] == ".":
			ans = min(ans, (min(x-1, y, H-x+1, W-y)+K-1)//K)
			stack.append([x,y+1,c])
print(ans+1)

Submission status: Wrong Answer

Solution code:
import math
import copy
temp=input().split()
H=int(temp[0])
W=int(temp[1])
K=int(temp[2])
A=[[i for i in input()] for j in range(H)]
place=[[K+2 for j in range(W)] for i in range(H)]
ans=0

si=0
sj=0
for i in range(H):
	for j in range(W):
		if A[i][j]=="S":
			si=i
			sj=j
			A[i][j]="."
			break

now=[[si,sj]]
place[si][sj]=0
next=[]
for i in range(1,K+1):
	for room in now:
		if A[room[0]-1][room[1]]=="." and place[room[0]-1][room[1]]>i:
			place[room[0]-1][room[1]]=i
			next.append([room[0]-1,room[1]])
			if room[0]==1:
				ans=-1
		if A[room[0]+1][room[1]]=="." and place[room[0]+1][room[1]]>i:
			place[room[0]+1][room[1]]=i
			next.append([room[0]+1,room[1]])
			if room[0]==H-2:
				ans=-1
		if A[room[0]][room[1]-1]=="." and place[room[0]][room[1]-1]>i:
			place[room[0]][room[1]-1]=i
			next.append([room[0],room[1]-1])
			if room[1]==1:
				ans=-1
		if A[room[0]][room[1]+1]=="." and place[room[0]][room[1]+1]>i:
			place[room[0]][room[1]+1]=i
			next.append([room[0],room[1]+1])
			if room[1]==W-2:
				ans=-1
	if ans==-1:
		break
	now=copy.deepcopy(next)
	next=[]
		
little=H+W
goodi=-1
goodj=-1
for i in range(H):
	for j in range(W):
		if place[i][j]<K+2:
			little=min(little,i,j,H-1-i,W-1-i)
			goodi=i
			goodj=j
print(math.ceil(little/K)+1)

Submission status: Wrong Answer

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

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

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

Q = [(sx, sy)]
while len(Q) > 0:
    x, y = Q.pop()
    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 abs(px - sx) + abs(py - sy) > K:
            continue
        if visited[py][px]:
            continue
        if MAP[py][px] == "#":
            continue
        Q.append((px, py))

d = 10000
for x in range(W):
    for y in range(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:
import math
temp=input().split()
H=int(temp[0])
W=int(temp[1])
K=int(temp[2])
A=[[i for i in input()] for j in range(H)]
place=[[K+2 for j in range(W)] for i in range(H)]

si=0
sj=0
for i in range(H):
	for j in range(W):
		if A[i][j]=="S":
			si=i
			sj=j
			A[i][j]="."
			break

now=[[si,sj]]
place[si][sj]=0
next=[]
for i in range(1,K+1):
	for room in now:
		if A[room[0]-1][room[1]]=="." and place[room[0]-1][room[1]]>i:
			place[room[0]-1][room[1]]=i
		if A[room[0]+1][room[1]]=="." and place[room[0]+1][room[1]]>i:
			place[room[0]+1][room[1]]=i
		if A[room[0]][room[1]-1]=="." and place[room[0]][room[1]-1]>i:
			place[room[0]][room[1]-1]=i
		if A[room[0]][room[1]+1]=="." and place[room[0]][room[1]+1]>i:
			place[room[0]][room[1]+1]=i
little=H+W
goodi=-1
goodj=-1
for i in range(H):
	for j in range(W):
		if place[i][j]<K+2:
			little=min(little,i,j,H-1-i,W-1-i)
			goodi=i
			goodj=j
print(math.ceil(little/K)+1)

Submission status: Wrong Answer

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

MAP = [raw_input() for _ in range(H)]

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

Q = [(sx, sy)]
V = set()
while len(Q) > 0:
    x, y = Q.pop()
    V.add((x, y))
    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 abs(px - sx) + abs(py - sy) > K:
            continue
        if (px, py) in V:
            continue
        if MAP[py][px] == "#":
            continue
        Q.append((px, py))

d = 10000
for x, y in V:
    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:
import math
temp=input().split()
H=int(temp[0])
W=int(temp[1])
K=int(temp[2])
A=[[i for i in input()] for j in range(H)]
place=[[K+2 for j in range(W)] for i in range(H)]

si=0
sj=0
for i in range(H):
	for j in range(W):
		if A[i][j]=="S":
			si=i
			sj=j
			A[i][j]="."
			break

now=[[si,sj]]
place[si][sj]=0
next=[]
for i in range(1,K+1):
	for room in now:
		if A[room[0]-1][room[1]]=="." and place[room[0]-1][room[1]]>i:
			place[room[0]-1][room[1]]=i
		if A[room[0]+1][room[1]]=="." and place[room[0]+1][room[1]]>i:
			place[room[0]+1][room[1]]=i
		if A[room[0]][room[1]-1]=="." and place[room[0]][room[1]-1]>i:
			place[room[0]][room[1]-1]=i
		if A[room[0]][room[1]+1]=="." and place[room[0]][room[1]+1]>i:
			place[room[0]][room[1]+1]=i
little=H+W
goodi=-1
goodj=-1
for i in range(H):
	for j in range(W):
		if place[i][j]<K+2:
			little=min(little,i,j,H-i,W-i)
			goodi=i
			goodj=j
print(math.ceil(little/K)+1)

Submission status: Wrong Answer

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

MAP = [raw_input() for _ in range(H)]

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

Q = [(sx, sy)]
V = set()
while len(Q) > 0:
    x, y = Q.pop()
    V.add((x, y))
    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 (px, py) in V:
            continue
        if MAP[py][px] == "#":
            continue
        Q.append((px, py))

d = 10000
for x, y in V:
    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:
from sys import stdin
rr = lambda: stdin.readline().strip()
rrM = lambda: map(int, rr().split())

OPEN, CLOSE, START = '.#S'
R, C, K = rrM()
A = [rr() for _ in xrange(R)]

#Move up to K first.  Then, you can move freely.
for r, row in enumerate(A):
    for c, val in enumerate(row):
        if val == START: break
    if val == START: break

def neighbors(r, c):
    for cr, cc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
        if 0<=cr<R and 0<=cc<C and A[cr][cc] == OPEN:
            yield cr, cc

def dist(r, c):
    return min(r,c,R-1-r,C-1,c)

from collections import deque
start = (r, c)
seen = {start}
queue = deque([(start, 0)])
node_dist = {}
while queue:
    node, depth = queue.popleft()
    node_dist[node] = depth
    for nei in neighbors(*node):
        if nei not in seen:
            seen.add(nei)
            queue.append((nei, depth+1))

#print seen

ans = 1e9
for r, c in seen:
    if node_dist[r, c] > K: continue
    delta = dist(r, c)
    #delta of 0 is bns = 0
    #delta of 1...K is bns 1
    #delta of K+1..2K is bns 2
    if delta == 0:
        bns = 0
    else:
        bns = 1 + (delta - 1)/K
    ans = min(ans, 1 + bns)
print ans

Submission status: Wrong Answer

Solution code:
from sys import stdin
rr = lambda: stdin.readline().strip()
rrM = lambda: map(int, rr().split())

OPEN, CLOSE, START = '.#S'
R, C, K = rrM()
A = [rr() for _ in xrange(R)]

#Move up to K first.  Then, you can move freely.
for r, row in enumerate(A):
    for c, val in enumerate(row):
        if val == START: break
    if val == START: break

def neighbors(r, c):
    for cr, cc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
        if 0<=cr<R and 0<=cc<C and A[cr][cc] == OPEN:
            yield cr, cc

def dist(r, c):
    return min(r,c,R-1-r,C-1,c)

from collections import deque
start = (r, c)
seen = {start}
queue = deque([(start, 0)])
while queue:
    node, depth = queue.popleft()
    if depth == K: break
    for nei in neighbors(*node):
        if nei not in seen:
            seen.add(nei)
            queue.append((nei, depth+1))

#print seen

ans = 1e9
for r, c in seen:
    delta = dist(r, c)
    #delta of 0 is bns = 0
    #delta of 1...K is bns 1
    #delta of K+1..2K is bns 2
    if delta == 0:
        bns = 0
    else:
        bns = 1 + (delta - 1)/K
    ans = min(ans, 1 + bns)
print ans

Submission status: Wrong Answer

Solution code:
import collections
h,w,k = map(int, input().split())
a = [[c for c in input()] for i in range(h)]

min_dis  = w*h
s = False
for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            s = (i, j)
            break
    if s:
        break

dq = collections.deque()
dq.append((0, s[0], s[1]))

moved = [[False for j in range(w)] for i in range(h)]
while dq:
    m, y, x = dq.popleft()
    if moved[y][x]:
        continue
    else:
        moved[y][x] = True
    if m >= k:
        continue
    if y == 0 or y == h-1 or x == 0 or x == w-1:
        print(1)
        exit()
    min_dis = min(min_dis, y, h-1-y, x, w-1-x)
    for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        if 0<=y+dy<h and 0<=x+dx<w and a[y+dy][x+dx] == '.' and not moved[y+dy][x+dx]:
            dq.append((m+1, y+dy, x+dx))
print(1+(min_dis+k-1)//k)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    h,w,k = LI()
    a = []
    st = None
    for i in range(h):
        s = S()
        if 'S' in s:
            st = [i, s.index('S')]
        a.append([c=='#' for c in s])

    def ns(k):
        i,j,t = k
        r = []
        if i < h-1:
            if a[i+1][j]:
                r.append((i+1,j,t+1))
            else:
                r.append((i+1,j,t))
        if j < w-1:
            if a[i][j+1]:
                r.append((i,j+1,t+1))
            else:
                r.append((i,j+1,t))
        if i > 0:
            if a[i-1][j]:
                r.append((i-1,j,t+1))
            else:
                r.append((i-1,j,t))
        if j > 0:
            if a[i][j-1]:
                r.append((i,j-1,t+1))
            else:
                r.append((i,j-1,t))
        return r


    def search(s):
        d = collections.defaultdict(lambda: inf)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for nu in ns(u):
                if v[nu] or nu[2] > h+w:
                    continue
                if v[(nu[0],nu[1],nu[2]-2)]:
                    continue
                vd = k + 1
                if d[nu] > vd:
                    d[nu] = vd
                    heapq.heappush(q, (vd, nu))

        return d

    d = search(tuple(st+[0]))
    r = inf
    for g,v in d.items():
        if 0 < g[0] < h-1 and 0 < g[1] < w-1:
            continue
        t = (v+k-1) // k + (g[2]+k-1) // k
        if t < r:
            r = t
    return r


print(main())

Submission status: Wrong Answer

Solution code:
from sys import stdin
rr = lambda: stdin.readline().strip()
rrM = lambda: map(int, rr().split())

OPEN, CLOSE, START = '.#S'
R, C, K = rrM()
A = [rr() for _ in xrange(R)]

#Move up to K first.  Then, you can move freely.
for r, row in enumerate(A):
    for c, val in enumerate(row):
        if val == START: break
    if val == START: break

def neighbors(r, c):
    for cr, cc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
        if 0<=cr<R and 0<=cc<C and A[cr][cc] == OPEN:
            yield cr, cc

def dist(r, c):
    return min(r,c,R-1-r,C-1,c)

from collections import deque
start = (r, c)
seen = {start}
queue = deque([(start, 0)])
while queue:
    node, depth = queue.popleft()
    if depth == K: break
    for nei in neighbors(*node):
        if nei not in seen:
            seen.add(nei)
            queue.append((node, depth+1))

ans = 1e9
for r, c in seen:
    delta = dist(r, c)
    #delta of 0 is bns = 0
    #delta of 1...K is bns 1
    #delta of K+1..2K is bns 2
    if delta == 0:
        bns = 0
    else:
        bns = 1 + (delta - 1)/K
    ans = min(ans, 1 + bns)
print ans

Submission status: Wrong Answer

Solution code:
from collections import deque
h, w, k = map(int, raw_input().split())
A = [raw_input() for i in xrange(h)]
sx = sy = 0
for i in xrange(h):
    idx = A[i].find('S')
    if idx != -1:
        sx = idx; sy = i
        break

deq = deque()
deq.append((0, (sx, sy)))

used = set([(sx, sy)])
dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while deq:
    cost, [x, y] = deq.popleft()
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if 0 <= nx < w and 0 <= ny < h:
            nkey = (nx, ny)
            if A[ny][nx] != '#' and nkey not in used:
                used.add(nkey)
                if cost + 1 < k:
                    deq.append((0, nkey))
ans = 10**18
for x, y in used:
    dx = min(x, w-1-x)
    dy = min(y, h-1-y)
    ans = min(ans, min(dx, dy))
print (ans+k-1)/k + 1

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
inf = 10**8
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 = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            node.append((i, j))
            dist[i][j] = 0

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


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: Time Limit Exceeded

Solution code:
import sys
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)


# Kマス消してKマス進めるの繰り返し
magic = 1
while True:
    node = memo
    memo = []
    magic += 1
    d = 0
    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 dist[nx][ny] >= inf:
                    dist[nx][ny] = magic
                    nxt.append((nx, ny))
        d += 1
        node = nxt
    memo.extend(node)