Buggy python submission (verdict: Time Limit Exceeded):

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)

Fixed submission:

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

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
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)

Buggy python submission (verdict: Time Limit Exceeded):

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)

Fixed submission:

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

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
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)

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p={(x,y)}
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    l[wx][wy]=1
    p.add((wx,wy))
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":

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

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

print(ans)

Fixed submission:

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

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
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)

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
h,w,k=map(int,input().split())
maze=[input()for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j;break
    else:
        continue
    break
ans=float("INF")
l=[[0]*w for i in range(h)]
p={(x,y)}
def dfs(wx,wy,cnt):
    if cnt>k:return 1
    if l[wx][wy]:return 1
    l[wx][wy]=1
    p.add((wx,wy))
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=wx+a<h and 0<=wy+s<w and maze[wx+a][wy+s]==".":

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

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

print(ans)

Fixed submission:

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

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
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)

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

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

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

print(ans)

Fixed submission:

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

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
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)

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:

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

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
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)

Buggy python submission (verdict: Time Limit Exceeded):
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)


Fixed submission:

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

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
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)