Problem p03725 (python)

Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

h,w,k=map(int,input().split())
MAP=[]
for i in range(h):
    s=list(input().strip())
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i,j
    MAP.append(s)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
q=deque()
q.append((sx,sy,k))
dist=float('inf')
Visited=[[False]*w for _ in range(h)]
Visited[sx][sy]=True
while len(q)>0:
    x,y,t=q.popleft()
    dist=min(dist,x,y,h-1-x,w-1-y)
    if dist==0:
        break
    if t>0:
        t-=1
        for dx,dy in delta:
            if MAP[x+dx][y+dy]=='.' and not Visited[x+dx][y+dy]:
                q.append((x+dx,y+dy,t))
                Visited[x+dx][y+dy]=True
print(1+ceil(dist/k))

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

def dist(h,w,x,y):
    return min(x-1,h-x,y-1,w-y)

h,w,k=map(int,input().split())
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s='#'+input().strip()+'#'
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j
    MAP.append(list(s))
MAP.append(A)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
P=[]
Visited=[[False]*(w+2) for _ in range(h+2)]
Visited[sx][sy]=True
q=deque()
q.append((sx,sy,k))
while q:
    x,y,t=q.popleft()
    if t<0:
        break
    P.append([x,y])
    t-=1
    for dx,dy in delta:
        if MAP[y+dy][x+dx]=='.' and not Visited[x+dx][y+dy]:
            q.append((y+dy,x+dx,t))
            Visited[x+dx][y+dy]=True
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

h,w,k=map(int,input().split())
MAP=[]
for i in range(h):
    s=list(input().strip())
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i,j
    MAP.append(s)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
q=deque()
q.append((sx,sy,k))
dist=float('inf')
Visited=[[False]*w for _ in range(h)]
Visited[sy][sx]=True
while len(q)>0:
    x,y,t=q.popleft()
    dist=min(dist,x,y,h-1-x,w-1-y)
    if dist==0:
        break
    if t>0:
        t-=1
        for dx,dy in delta:
            if MAP[x+dx][y+dy]=='.' and not Visited[x+dx][y+dy]:
                q.append((x+dx,y+dy,t))
                Visited[x+dx][y+dy]=True
print(1+ceil(dist/k))

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

h,w,k=map(int,input().split())
MAP=[]
for i in range(h):
    s=list(input().strip())
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i,j
    MAP.append(s)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
q=deque()
q.append((sx,sy,k))
dist=float('inf')
Visited=[[False]*w for _ in range(h)]
Visited[sy][sx]=True
while q:
    x,y,t=q.popleft()
    dist=min(dist,x,y,w-1-x,h-1-y)
    if not dist:
        break
    if t:
        t-=1
        for dx,dy in delta:
            if MAP[x+dx][y+dy]=='.' and not Visited[x+dx][y+dy]:
                q.append((x+dx,y+dy,t))
                Visited[x+dx][y+dy]=True
print(1+ceil(dist/k))

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

def dist(h,w,x,y):
    return min(x-1,h-x,y-1,w-y)

h,w,k=map(int,input().split())
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s='#'+input().strip()+'#'
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j
    MAP.append(list(s))
MAP.append(A)
delta=[[1,0],[0,1],[-1,0],[0,-1]]
P=[]
q=deque()
q.append((sx,sy,k))
while q:
    x,y,t=q.popleft()
    if t<0:
        break
    P.append([x,y])
    t-=1
    for dx,dy in delta:
        if MAP[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx,t))
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

def dist(h,w,x,y):
    return min(x-1,h-x,y-1,w-y)

h,w,k=map(int,input().split())
delta=[[1,0],[0,1],[-1,0],[0,-1]]
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s='#'+input().strip()+'#'
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j
    MAP.append(list(s))
MAP.append(A)
d=[[-1]*(w+2) for _ in range(h+2)]
d[sy][sx]=0
P=[]
q=deque()
q.append((sx,sy))
while q:
    x,y=q.popleft()
    if d[x][y]>k:
        break
    P.append([x,y])
    for dx,dy in delta:
        if d[y+dy][x+dx]==-1 and MAP[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]=d[y][x]+1
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
from collections import deque
from math import ceil

def dist(h,w,x,y):
    return min(x-1,h-x,y-1,w-y)

h,w,k=map(int,input().split())
delta=[[1,0],[0,1],[-1,0],[0,-1]]
MAP=[]
A=['#']*(w+2)
MAP.append(A)
for i in range(h):
    s=input()
    for j,t in enumerate(s):
        if t=='S':
            sx,sy=i+1,j+1
    MAP.append(list(s))
MAP.append(A)
d=[[-1]*(w+2) for _ in range(h+2)]
d[sy][sx]=0
P=[]
q=deque()
q.append((sx,sy))
while q:
    x,y=q.popleft()
    if d[x][y]>k:
        break
    P.append([x,y])
    for dx,dy in delta:
        if d[y+dy][x+dx]==-1 and MAP[y+dy][x+dx]=='.':
            q.append((y+dy,x+dx))
            d[y+dy][x+dx]=d[y][x]+1
ans=float('inf')
for x,y in P:
    ans=min(ans,1+ceil(dist(h,w,x,y)/k))
print(ans)