Problem p03436 (python)

Fixed submission:
import sys

def wfs(queue, S, step, goal):
    next_queue = set()
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.add((i+1, j))
        if S[i-1][j] == '.':
            next_queue.add((i-1, j))
        if S[i][j+1] == '.':
            next_queue.add((i, j+1))
        if S[i][j-1] == '.':
            next_queue.add((i, j-1))

    if len(next_queue) == 0:
        return -1
    else:
        next_queue = list(set(next_queue))
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    black = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        black += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    init = set([(1, 1)])
    minstep = wfs(init, S, 0, (H, W))
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - black)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        next_queue = list(set(next_queue))
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c for c in input().strip()]
        init += sum([c == '#' for c in s])
        S.append(['#'] + s + ['#'])
    S = [['#'] * (W+2)] + S + [['#'] * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys

def wfs(queue, S, step, goal):
    next_queue = []
    for q in queue:
        if q == goal:
            return step+1

        i, j = q[0], q[1]
        S[i][j] = '#'

        if S[i+1][j] == '.':
            next_queue.append([i+1, j])
        if S[i-1][j] == '.':
            next_queue.append([i-1, j])
        if S[i][j+1] == '.':
            next_queue.append([i, j+1])
        if S[i][j-1] == '.':
            next_queue.append([i, j-1])

    if len(next_queue) == 0:
        return -1
    else:
        return wfs(next_queue, S, step+1, goal)


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = input().strip()
        init += s.count('#')
        S.append('#' + s + '#')
    S = ['#' * (W+2)] + S + ['#' * (W+2)]
    minstep = wfs([[1,1]], S, 0, [H, W])
    if minstep == -1:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys

def f(pos, S, step, R, goal):
    i, j = pos[0], pos[1]
    if i >= goal[0]+1 or i < 0 or j >= goal[1]+1 or j < 0:
        return 10**5
    if S[i][j]:
        return 10**5
    if pos == goal:
        return step

    if step > R[i][j]:
        return 10**5
    else:
        R[i][j] = step
        return min(f([i+1, j], S, step+1, R, goal),
                   f([i-1, j], S, step+1, R, goal),
                   f([i, j+1], S, step+1, R, goal),
                   f([i, j-1], S, step+1, R, goal))

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    S = []
    init = 0
    for _ in range(H):
        s = [c == '#' for c in input().strip()]
        init += sum(s)
        S.append(s)
    R = [[10**5 for _ in range(W)] for _ in range(H)]
    R[0][0] = 1
    minstep = f([0,0], S, 1, R, [H-1, W-1])
    if minstep == 10**5:
        print(-1)
    else:
        print(H*W - minstep - init)


if __name__ == '__main__':
    main()