Problem p03436 (python)

Fixed submission:
from collections import defaultdict, deque
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

dhw = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
]

# h,w,dist
dq = deque([(0, 0, 0)])
# h,w
queued = {(0, 0)}

fdist = -1
while dq:
    h, w, dist = dq.popleft()
    
    if h == H - 1 and w == W - 1:
        fdist = dist
        break
        
    for dh, dw in dhw:
        nh = h + dh
        nw = w + dw
        ndist = dist + 1

        if (nh,nw) in queued:
            continue
        if not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if sss[nh][nw]:
            continue

        dq.append((nh, nw, ndist))
        queued.add((nh, nw))

if fdist == -1:
    print(-1)
else:
    print(H * W - sum(sum(sss,[])) - fdist - 1)

Buggy submission (verdict: Runtime Error):
from collections import defaultdict, deque
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

dhw = [
    [0,1],
    [1,0],
    [0,-1],
    [-1,0],
]

dists = defaultdict(lambda: defaultdict(lambda: float('inf')))
passed = defaultdict(lambda: defaultdict(lambda: False))

# h,w,dist
dq = deque([(0,0)])
dists[0][0] = 0

while dq:
    h, w = dq.popleft()
    dist = dists[h][w]
    passed[h][w] = True
    
    if h == H - 1 and w == W - 1:
        fdist = dist
        break
        
    for dh, dw in dhw:
        nh = h + dh
        nw = w + dw
        ndist = dist + 1
        if not(0 <= nh < H) or not(0 <= nw < W):
            continue
        if passed[nh][nw]:
            continue
        if sss[nh][nw]:
            continue
        dists[nh][nw] = min(dists[nh][nw], ndist)
        dq.append((nh,nw))

print(H * W - sum(sum(sss,[])) - fdist - 1)

Buggy submission (verdict: Runtime Error):
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

from functools import lru_cache
dhw = [
    [0,1],
    [0,-1],
    [1,0],
    [-1,0],
]
passed = set()

@lru_cache(maxsize=None)
def calc(h,w):
    passed.add((h,w))
    if h == H-1 and w == W-1:
        return 1
    ans = float('inf')
    for dh, dw in dhw:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and sss[nh][nw]==0 and ((nh,nw) not in passed or dh+dw>0):
            ans = min(ans, calc(nh,nw) + 1)
    return ans
result = calc(0,0)
if calc(0,0) == float('inf'):
    print(-1)
else:
    print(H * W - sum(map(sum, sss)) - calc(0,0))

Buggy submission (verdict: Runtime Error):
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

from functools import lru_cache
dhw = [
    [0,1],
    [0,-1],
    [1,0],
    [-1,0],
]
passed = set()

@lru_cache(maxsize=None)
def calc(h,w):
    passed.add((h,w))
    if h == H-1 and w == W-1:
        return 1
    ans = float('inf')
    for dh, dw in dhw:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and sss[nh][nw]==0 and ((nh,nw) not in passed or dh+dw>0):
            ans = min(ans, calc(nh,nw) + 1)
    return ans

print(H * W - sum(map(sum, sss)) - calc(0,0))

Buggy submission (verdict: Runtime Error):
hwsss = [s.rstrip() for s in open(0)]
H,W = map(int, hwsss[0].split())
sss = [[int(c=='#') for c in list(l)] for l in hwsss[1:]]

from functools import lru_cache
dhw = [
    [0,1],
    [1,0],
    [0,-1],
    [-1,0],
]
passed = set()

@lru_cache(maxsize=None)
def calc(h,w):
    passed.add((h,w))
    if h == H-1 and w == W-1:
        return 1
    ans = float('inf')
    for dh, dw in dhw:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and (nh,nw) not in passed and sss[nh][nw]==0:
            ans = min(ans, calc(nh,nw) + 1)
    return ans

print(H * W - sum(map(sum, sss)) - calc(0,0))