Problem p02735 (python)

Fixed submission:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 5
    # dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
    dp = [[INF] * W for _ in range(H)]

    if maze[0][0] == '#':
        dp[0][0] = 1
    else:
        dp[0][0] = 0

    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '#':
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[H - 1][W - 1])


resolve()

Buggy submission (verdict: Runtime Error):
H, W = map(int, input().split())
maze = [[_ for _ in input()] for _ in range(W)]
INF = 10 ** 5

# dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
dp = [[INF] * W for _ in range(H)]

if maze[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        for [dy, dx] in [[1, 0], [0, 1]]:
            ny, nx = i + dy, j + dx
            if ny >= H or nx >= W:
                continue
            else:
                if maze[i][j] == '.' and maze[ny][nx] == '#':
                    dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                else:
                    dp[ny][nx] = min(dp[ny][nx], dp[i][j])
print(dp[H - 1][W - 1])

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    H, W = map(int, input().split())
    maze = [[_ for _ in input()] for _ in range(W)]
    INF = 10 ** 10
    # dp[i][j]:=(i,j)に到達するまでに黒壁を壊す回数の最小値
    dp = [[INF] * W for _ in range(H)]

    if maze[0][0] == '#':
        dp[0][0] = 1
    else:
        dp[0][0] = 0

    for i in range(H):
        for j in range(W):
            for [dy, dx] in [[1, 0], [0, 1]]:
                ny, nx = i + dy, j + dx
                if ny >= H or nx >= W:
                    continue
                else:
                    if maze[i][j] == '.' and maze[ny][nx] == '#':
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j] + 1)
                    else:
                        dp[ny][nx] = min(dp[ny][nx], dp[i][j])
    print(dp[W-1][H-1])


resolve()

Buggy submission (verdict: Runtime Error):
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    H,W=map(int,input().split())
    maze=[[_ for _ in input()] for _ in range(H)]

    from collections import deque

    sy, sx = 1,1
    gy, gx = H,W
    sy, sx, gy, gx = sy - 1, sx - 1, gy - 1, gx - 1

    maze = [input() for i in range(H)]
    visited = [[-1] * W for j in range(H)]


    def bfs(maze, visited, sy, sx, gy, gx):
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited
            for j, k in ([1, 0], [0, 1]):
                ny, nx = y + j, x + k
                if 0 <= ny < H and 0 <= nx < W and visited[nx][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])

    for i in range(H):
        for j in range(W):
            if visited[i][j]


    print(bfs(maze, visited, sy, sx, gy, gx))



resolve()