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

Solution code:
from collections import deque

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

D = [[1 for i in range(W)] for j in range(H)]

for x in range(H):
    for y in range(W):
        if S[x][y] == 'S':
            sx = x
            sy = y

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

ans = float('inf')

q = deque([[sx, sy, 0]])

while len(q) != 0:
    x, y, cnt = q.popleft()
    if cnt > K:
        break
    D[x][y] = 0
    tmp = min(x, y , H - x - 1, W - y - 1)
    if tmp != 0:
        tmp = (tmp - 1) // K
        tmp += 2
    else:
        tmp = 1
    ans = min(ans, tmp)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '#' and D[nx][ny]:
            q.append([nx, ny, cnt + 1])

print(ans)

Submission status: Time Limit Exceeded

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

def main():
    h,w,k = map(int,ipt().split())
    A = [input() for _ in range(h)]
    for i,ai in enumerate(A):
        if "S" in ai:
            si = i
            sj = ai.find("S")
            break

    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    bt = [[10**10]*w for i in [0]*h]
    t = [[10**10]*w for i in [0]*h]
    bt[si][sj] = 0
    t[si][sj] = 0
    q = queue.Queue()
    q.put((si,sj))
    while not q.empty():
        qi,qj = q.get()
        for di,dj in dir:
            if 0 <= qi+di <= h-1 and 0 <= qj+dj <= w-1:
                if A[qi+di][qj+dj] == "#" and bt[qi+di][qj+dj] > bt[qi][qj]+1:
                    bt[qi+di][qj+dj] = bt[qi][qj]+1
                    q.put((qi+di,qj+dj))
                elif A[qi+di][qj+dj] == "." and bt[qi+di][qj+dj] > bt[qi][qj]:
                    bt[qi+di][qj+dj] = bt[qi][qj]
                    q.put((qi+di,qj+dj))

    nq = queue.Queue()
    nq.put((si,sj))
    ans = 1
    while True:
        while not nq.empty():
            qi,qj = nq.get()
            q.put((qi,qj))
        while not q.empty():
            qi,qj = q.get()
            if qi == 0 or qi == h-1 or qj == 0 or qj == w-1:
                print(ans)
                exit()
            for di,dj in dir:
                if t[qi+di][qj+dj] > t[qi][qj]+1:
                    if t[qi][qj] == ans*k or bt[qi+di][qj+dj] > (ans-1)*k:
                        nq.put((qi+di,qj+dj))
                        t[qi+di][qj+dj] = ans*k+1
                    else:
                        t[qi+di][qj+dj] = t[qi][qj]+1
                        q.put((qi+di,qj+dj))
        ans += 1

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

for h in range(H):
  for w in range(W):
    if A[h][w] == 'S':
      sx, sy = h, w

INF = 1000
dist = [[INF for w in range(W)] for h in range(H)]
dist[sx][sy] = 0


dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
start = []
d = deque([[sx, sy]])
while d:
  x, y = d.popleft()
  for dx, dy in dxy:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and dist[xx][yy]==INF:
      if A[xx][yy] == '.':
        dist[xx][yy] = dist[x][y] + 1
        d.append([xx, yy])
        if dist[xx][yy] <= K:
          start.append([xx, yy])

ans = min(-(-(H-1-sx)//K)+1, -(-sx//K)+1, -(-(W-1-sy)//K)+1, -(-sy//K)+1)
for x, y in start:
  ans = min(ans, -(-(W-1 - y)//K) + 1) # 右
  ans = min(ans, -(-y//K) + 1) # 左
  ans = min(ans, -(-(H-1 - x)//K) + 1) # 下
  ans = min(ans, -(-x//K) + 1) # 上

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p={(x,y)}
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.add((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

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

Submission status: Time Limit Exceeded

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=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
p=[(x,y)]
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.append((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

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

Submission status: Time Limit Exceeded

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
l=[[700000,700000]for i in range(h*w)]
l[w*x+y]=[0,0]
from collections import deque
dq=deque([(x,y)])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
while len(dq):
    a,b=dq.popleft()
    for c,d in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+c<h and 0<=b+d<w:
            op,cl=l[w*a+b]
            if maze[a+c][b+d]=="#":cl+=1
            else:op+=1
            if -(-l[(a+c)*w+b+d][0]//k)-(-l[(a+c)*w+b+d][1]//k)>=-(-op//k)-(-cl//k):
                l[(a+c)*w+b+d]=[op,cl]
                dq.append((a+c,b+d))
ans=min(min((s+k)//k+(d+k-1)//k for s,d in l[0:w]),min((s+k)//k+(d+k-1)//k for s,d in l[-w:]),min((s+k)//k+(d+k-1)//k for s,d in l[0::w]),min((s+k)//k+(d+k-1)//k for s,d in l[w-1::w]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

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=[(0,s[0],s[1])]
heapq.heapify(que)
while que:
    count,posx,posy=heapq.heappop(que)
    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))
            heapq.heappush(que,(count+1,nx,ny))


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

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=((1,0,K),i,l.index('S'))
q=[S]
from heapq import heappop,heappush
n=((0,1),(0,-1),(1,0),(-1,0))
v=[[0]*W for i in range(H)]
v[S[1]][S[2]]=1
a=999
#M=[[999]*H for i in range(W)]
while q:
    (s,m,o),i,j=heappop(q)
    #M[i][j]=min(s,M[i][j])
    if i in (0,H-1) or j in (0,W-1):
        a=min(a,s)
    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]=='.':
                if m<K:
                    heappush(q,((s,m+1,o),i+x,j+y))
                else:
                    heappush(q,((s+1,1,o-K),i+x,j+y))
            elif A[i+x][j+y]=='#':
                if m<K and o<K:
                    heappush(q,((s,m+1,o+1),i+x,j+y))
                else:
                    heappush(q,((s+1,1,o-K+1),i+x,j+y))
print(a)
#print(*M,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

G = [list(input()) for _ in range(H)]
check = [[-1] * (W) for _ in range(H)]

que = deque()

flag = False
for h in range(H):
    for w in range(W):
        if G[h][w] == 'S':
            que.append((h, w))
            flag = True
            break
    if flag:
        break

x_min = h
x_max = h

y_min = w
y_max = w

check[h][w] = 0
while que:
    tmp = que.popleft()
    
    x = tmp[0]
    y = tmp[1]
    
    now_ = check[x][y]
    if now_ == K:
        continue

    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if G[nx][ny] == '#':
            continue
        if check[nx][ny] == -1:
            check[nx][ny] = now_ + 1
            que.append((nx, ny))
            
            x_min = min(x_min, nx)
            x_max = max(x_max, nx)

            y_min = min(y_min, ny)
            y_max = max(y_max, ny)

ans = 10 ** 18
ans = min(ans, (x_min + K - 1) // K + 1)
ans = min(ans, (H - x_max - 1 + K - 1) // K + 1)
ans = min(ans, (y_min + K - 1) // K + 1)
ans = min(ans, (W - y_max - 1 + K - 1) // K + 1)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = map(int,input().split())
l = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == "S":
            s = [0,[i,j],0,0]
    l.append(a)
ans = h*w
dp = [[[h*w,0,0] for i in range(w)] for i in range(h)]
dp[s[1][0]][s[1][1]] = [0,0,0]
d = [s]
b = [[0,1],[1,0],[-1,0],[0,-1]]
heapq.heapify(d)
while len(d):
    spell1,now,steps1,op1 = heapq.heappop(d)
    if ans < spell1:
        break
    for i in b:
        spell = spell1
        steps = steps1
        op = op1
        #print(now[0]+i[0],now[1]+i[1])
        nex = [now[0]+i[0],now[1]+i[1]]
        if l[nex[0]][nex[1]] == ".":
            if steps > 0:
                steps -= 1
            else:
                spell += 1
                steps += k-1
        else:
            if op > 0:
                if steps > 0:
                    steps -= 1
                    op -= 1
                else:
                    op -= 1
                    steps += k-1
                    spell += 1
            else:
                if steps == 0:
                    steps += k-1
                    spell += 2
                    op += k-1
                else:
                    op += k-1
                    steps += k-1
                    spell += 1
        if nex[0] == 0 or nex[0] == h-1 or nex[1] == 0 or nex[1] == w-1:
            ans = min(ans,spell)
        else:
            dp0 = dp[nex[0]][nex[1]]
            if dp0[0] > spell:
                heapq.heappush(d,[spell,nex,steps,op])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
h,w,k = map(int,input().split())
l = []
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == "S":
            s = [0,[i,j],0,0]
    l.append(a)
ans = h*w
dp = [[[h*w,0,0] for i in range(w)] for i in range(h)]
dp[s[1][0]][s[1][1]] = [0,0,0]
d = [s]
b = [[0,1],[1,0],[-1,0],[0,-1]]
heapq.heapify(d)
while len(d):
    spell1,now,steps1,op1 = heapq.heappop(d)
    if ans < spell1:
        break
    for i in b:
        spell = spell1
        steps = steps1
        op = op1
        #print(now[0]+i[0],now[1]+i[1])
        nex = [now[0]+i[0],now[1]+i[1]]
        if l[nex[0]][nex[1]] == ".":
            if steps > 0:
                steps -= 1
            else:
                spell += 1
                steps += k-1
        else:
            if op > 0:
                if steps > 0:
                    steps -= 1
                    op -= 1
                else:
                    op -= 1
                    steps += k-1
                    spell += 1
            else:
                if steps == 0:
                    steps += k-1
                    spell += 2
                    op += k-1
                else:
                    op += k-1
                    steps += k-1
                    spell += 1
        if nex[0] == 0 or nex[0] == h-1 or nex[1] == 0 or nex[1] == w-1:
            ans = min(ans,spell)
        else:
            dp0 = dp[nex[0]][nex[1]]
            if dp0[0] > spell or dp0[1] < steps or dp0[1] < op:
                heapq.heappush(d,[spell,nex,steps,op])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

INF = 1010101010

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

h, w, k = map(int, input().split())
a = [list(input()) for _ in range(h)]

sy = -1
sx = -1
for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            sy = i
            sx = j

cost = [[INF for j in range(w)] for i in range(h)]
cost[sy][sx] = 0
que = queue.Queue()
que.put((sy, sx, 0))

while not que.empty():
    now = que.get()

    if cost[now[0]][now[1]] < now[2]:
        continue

    for i in range(4):
        ny = now[0] + dy[i]
        nx = now[1] + dx[i]
        nc = now[2] + 1

        if 0 <= ny < h and 0 <= nx < w and a[ny][nx] != '#'and nc < cost[ny][nx]:
            cost[ny][nx] = nc
            que.put((ny, nx, nc))

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def calc(x,y):
  cnt1=(x+k-1)//k
  cnt2=(w-1-x+k-1)//k
  cnt3=(y+k-1)//k
  cnt4=(h-1-y+k-1)//k
  return min(cnt1,cnt2,cnt3,cnt4)

h,w,k=map(int,input().split())
boards=[tuple(input()) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if boards[i][j]=='S':
      sx=j
      sy=i
      break
q=collections.deque()
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
q.append((sx,sy,0))
ans=1+calc(sx,sy)
while 1:
  if len(q)==0:
    break
  tx,ty,cnt=q.popleft()
  if cnt==k+1:
    break
  ans=min(ans,1+calc(tx,ty))
  if tx!=0 and boards[ty][tx-1]!='#' and checked[ty][tx-1]==0:
    checked[ty][tx-1]=1
    q.append((tx-1,ty,cnt+1))
  if tx!=w-1 and boards[ty][tx+1]!='#' and checked[ty][tx+1]==0:
    checked[ty][tx+1]=1
    q.append((tx+1,ty,cnt+1))
  if ty!=0 and boards[ty-1][tx]!='#' and checked[ty-1][tx]==0:
    checked[ty-1][tx]=1
    q.append((tx,ty-1,cnt+1))
  if ty!=h-1 and boards[ty+1][tx]!='#' and checked[ty+1][tx]==0:
    checked[ty+1][tx]=1
    q.append((tx,ty+1,cnt+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def calc(x,y):
  cnt1=(x+k-1)//k
  cnt2=(w-1-x+k-1)//k
  cnt3=(y+k-1)//k
  cnt4=(h-1-y+k-1)//k
  return min(cnt1,cnt2,cnt3,cnt4)

h,w,k=map(int,input().split())
boards=[list(input()) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if boards[i][j]=='S':
      sx=j
      sy=i
      break
q=collections.deque()
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
q.append((sx,sy,0))
ans=1+calc(sx,sy)
while 1:
  if len(q)==0:
    break
  tx,ty,cnt=q.popleft()
  if cnt==k+1:
    break
  ans=min(ans,1+calc(tx,ty))
  if tx!=0 and boards[ty][tx-1]!='#' and checked[ty][tx-1]==0:
    checked[ty][tx-1]=1
    q.append((tx-1,ty,cnt+1))
  if tx!=w-1 and boards[ty][tx+1]!='#' and checked[ty][tx+1]==0:
    checked[ty][tx+1]=1
    q.append((tx+1,ty,cnt+1))
  if ty!=0 and boards[ty-1][tx]!='#' and checked[ty-1][tx]==0:
    checked[ty-1][tx]=1
    q.append((tx,ty-1,cnt+1))
  if ty!=h-1 and boards[ty+1][tx]!='#' and checked[ty+1][tx]==0:
    checked[ty+1][tx]=1
    q.append((tx,ty+1,cnt+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w,k = map(int, input().split())
g = [list(input()) for _ in range(h)]
ans = h*w
for i in range(h):
  if 'S' in g[i]:
    sx = g[i].index('S')
    sy = i
    break
g[sy][sx] = 0
q = deque()
q.append(sy*w+sx)
while q:
  v = q.popleft()
  y,x = v//w, v%w
  cur = min((y-1)//k, (x-1)//k, (h-y-2)//k, (w-x-2)//k) + 2
  if ans > cur:
    ans = cur
  if g[y][x] < k:
    for dx,dy in ((0,1),(1,0),(0,-1),(-1,0)):
      nx = x+dx; ny = y+dy
      if 0 <= nx < w and 0 <= ny < h and g[ny][nx] == '.':
        g[ny][nx] = g[y][x] + 1
        q.append(ny*w+nx)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):
#    debug_print(maze)
    distance = [[inf]*w for _ in range(h)]
    def bfs():
        queue = []
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#'):
                    if distance[ny][nx]<=distance[y][x]+1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)
#    print(D)
    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Submission status: Time Limit Exceeded

Solution code:
Dy = [1,0,-1,0]
Dx = [0,-1,0,1]

H, W, K = map(int, input().split())
A = [input() for _ in range(H)]
Closed = [[False]*W for _ in range(H)]
for y, a in enumerate(A):
    for x, aa in enumerate(a):
        if aa=="S":
            ys, xs = y, x
q = [(ys, xs)]
Closed[ys][xs] = True
reachable = [(ys, xs)]
for _ in range(K):
    q_new = []
    for y_old, x_old in q:
        for dy, dx in zip(Dy, Dx):
            y, x = y_old + dy, x_old + dx
            if not (0<=y<H and 0<=x<W):
                continue
            if not Closed[y][x] and A[y][x]==".":
                Closed[y][x] = True
                reachable.append((y, x))
                q_new.append((y, x))
    q = q_new
mi = float("inf")
for y, x in reachable:
    mi = min(mi, x, y, W-1-x, H-1-y)
print((mi-1)//K+2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        A[Si][Sj] = "."
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    if A[i][j] == "#":
        continue
    A[i][j] = "#"

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            Q.append((cnt + 1, ni, nj))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0

ans = INF

Q = deque([(0, Si, Sj)])
while Q:
    dist, i, j = Q.popleft()
    if dist > K:
        break

    A[i][j] = "#"

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist > K or ans == 0:
        break

    distance = dist + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            Q.append((distance, ni, nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0

ans = INF

Q = deque([(0, Si, Sj)])
while Q:
    dist, i, j = Q.popleft()
    if dist > K:
        break

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist > K or ans == 0:
        break

    distance = dist + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((distance, ni, nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0

ans = INF

Q = deque([(0, Si, Sj)])
while Q:
    dist, i, j = Q.popleft()
    if dist > K:
        break

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist > K:
        break

    distance = dist + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "#"
        Q.append((distance, ni, nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if ans == 0:
        break

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W) or A[ni][nj] == "#":
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

INF = float("inf")

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

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W) or A[ni][nj] == "#":
            continue

        A[ni][nj] = "#"

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)