Problem p03053 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while 0 < len(queue):
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)

        rem -= 1
        #if rem == 0:
        #    break

        for dx, dy in zip([0, 1, 0, -1], [1, 0, -1, 0]):
            nx = j + dx
            ny = i + dy
            if (0 <= nx < W) and (0 <= ny < H):
                queue.append((ny, nx, n + 1))
        #if 0 < j:
        #    queue.append((i, j - 1, n + 1))
        #if j < W - 1:
        #    queue.append((i, j + 1, n + 1))
        #if 0 < i:
        #    queue.append((i - 1, j, n + 1))
        #if i < H - 1:
        #    queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while 0 < len(queue):
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)

        rem -= 1
        #if rem == 0:
        #    break

        for dx, dy in zip([0, 1, 0, -1], [1, 0, -1, 0]):
            nx = j + dx
            ny = i + dy
            if (0 <= nx < W) and (0 <= ny < H):
                queue.append((ny, nx, n + 1))
        #if 0 < j:
        #    queue.append((i, j - 1, n + 1))
        #if j < W - 1:
        #    queue.append((i, j + 1, n + 1))
        #if 0 < i:
        #    queue.append((i - 1, j, n + 1))
        #if i < H - 1:
        #    queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while 0 < len(queue):
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)

        rem -= 1
        #if rem == 0:
        #    break

        for dx, dy in zip([0, 1, 0, -1], [1, 0, -1, 0]):
            nx = j + dx
            ny = i + dy
            if (0 <= nx < W) and (0 <= ny < H):
                queue.append((ny, nx, n + 1))
        #if 0 < j:
        #    queue.append((i, j - 1, n + 1))
        #if j < W - 1:
        #    queue.append((i, j + 1, n + 1))
        #if 0 < i:
        #    queue.append((i - 1, j, n + 1))
        #if i < H - 1:
        #    queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while 0 < len(queue):
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)

        rem -= 1
        #if rem == 0:
        #    break

        for dx, dy in zip([0, 1, 0, -1], [1, 0, -1, 0]):
            nx = j + dx
            ny = i + dy
            if (0 <= nx < W) and (0 <= ny < H):
                queue.append((ny, nx, n + 1))
        #if 0 < j:
        #    queue.append((i, j - 1, n + 1))
        #if j < W - 1:
        #    queue.append((i, j + 1, n + 1))
        #if 0 < i:
        #    queue.append((i - 1, j, n + 1))
        #if i < H - 1:
        #    queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i,l in enumerate(A):
        for j, c in enumerate(l):
            if c == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while queue:
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)

        rem -= 1
        if rem == 0:
            break

        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < W - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < H - 1:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    for i,l in enumerate(A):
        for j, c in enumerate(l):
            if c == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while queue:
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True

        ret = max(ret, n)
        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < W - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < H - 1:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    for i,l in enumerate(A):
        for j, c in enumerate(l):
            if c == '#':
                queue.append((i, j, 0))
    
    ret = 0
    visited = [[False] * W for _ in range(H)]
    while queue:
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True

        ret = max(ret, n)
        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < H - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < W - 1:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    holes = [[float('inf')] * W for _ in range(H)]
    for i,l in enumerate(A):
        for j, c in enumerate(l):
            if c == '#':
                holes[i][j] = 0

    for j in range(1, W):
        holes[0][j] = min(holes[0][j], holes[0][j-1] + 1)
    for i in range(1, H):
        holes[i][0] = min(holes[i][0], holes[i - 1][0] + 1)
    for i in range(1, H):
        for j in range(1, W):
            holes[i][j] = min(holes[i][j], holes[i-1][j] + 1, holes[i][j-1] + 1)

    ret = -float('inf')
    for j in range(W - 2, -1, -1):
        holes[H - 1][j] = min(holes[H - 1][j], holes[H - 1][j+1] + 1)
        ret = max(ret, holes[H - 1][j])
    for i in range(H - 2, -1, -1):
        holes[i][-1] = min(holes[i][-1], holes[i + 1][-1] + 1)
        ret = max(ret, holes[i][-1])
    for i in range(H - 2, -1, -1):
        for j in range(W - 2, -1, -1):
            holes[i][j] = min(holes[i][j], holes[i+1][j] + 1,  holes[i][j+1] + 1)
            ret = max(ret, holes[i][j])
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    holes = [[float('inf')] * W for _ in range(H)]
    for i,l in enumerate(A):
        for j, c in enumerate(l):
            if c == '#':
                holes[i][j] = 0
    for i in range(H):
        for j in range(1, W):
            holes[i][j] = min(holes[i][j], holes[i][j-1] + 1)
        for j in range(W - 2, -1, -1):
            holes[i][j] = min(holes[i][j], holes[i][j+1] + 1)

    for i in range(1, H):
        for j in range(W):
            holes[i][j] = min(holes[i][j], holes[i-1][j] + 1)
    for i in range(H - 2, -1, -1):
        for j in range(W):
            holes[i][j] = min(holes[i][j], holes[i+1][j] + 1)

    ret = -float('inf')
    for l in holes:
        ret = max(ret, max(l))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    holes = [[float('inf')] * W for _ in range(H)]
    for i,l in enumerate(A):
        for j, c in enumerate(l):
            if c == '#':
                holes[i][j] = 0
    for i in range(H):
        for j in range(1, W):
            holes[i][j] = min(holes[i][j], holes[i][j-1] + 1)
        for j in range(W - 2, -1, -1):
            holes[i][j] = min(holes[i][j], holes[i][j+1] + 1)

    for j in range(W):
        for i in range(1, H):
            holes[i][j] = min(holes[i][j], holes[i-1][j] + 1)
        for i in range(H - 2, -1, -1):
            holes[i][j] = min(holes[i][j], holes[i+1][j] + 1)

    ret = -float('inf')
    for i in range(H):
        for j in range(W):
            ret = max(ret, holes[i][j])
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(H: int, W: int, A: "List[str]"):
    holes = [[float('inf')] * W for _ in range(H)]
    for i,l in enumerate(A):
        for j, c in enumerate(l):
            if c == '#':
                holes[i][j] = 0
    for i in range(H):
        for j in range(1, W):
            holes[i][j] = min(holes[i][j], holes[i][j-1] + 1)
        for j in range(W - 2, -1, -1):
            holes[i][j] = min(holes[i][j], holes[i][j+1] + 1)

    for j in range(W):
        for i in range(1, H):
            holes[i][j] = min(holes[i][j], holes[i-1][j] + 1)
        for i in range(H - 2, -1, -1):
            holes[i][j] = min(holes[i][j], holes[i+1][j] + 1)

    ret = -float('inf')
    for i in range(H):
        for j in range(W):
            ret = max(ret, holes[i][j])
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(W) ]  # type: "List[str]"
    result = solve(H, W, A)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()