Submission #11057884


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

H,W = map(int,readline().split())
S = ''.join(read().decode().split())

INF = 10 ** 9
N = H*W
U = 250
dp = [[INF] * U for _ in range(N)]
# そのマスをいじる回数 → 総回数の最小値
dp[0] = list(range(U))
for n in range(H*W):
    for i in range(U-1,0,-1):
        if dp[n][i-1]> dp[n][i]:
            dp[n][i-1] = dp[n][i]
    for i in range(1,U):
        if dp[n][i-1] + 1 < dp[n][i]:
            dp[n][i] = dp[n][i-1] + 1
    s = S[n]
    if s == '#':
        for i in range(0,U,2):
            dp[n][i] = INF
    else:
        for i in range(1,U,2):
            dp[n][i] = INF
    x,y = divmod(n,W)
    to = []
    if y < W - 1:
        to.append(n+1)
    if x < H - 1:
        to.append(n+W)
    for m in to:
        for i in range(U):
            if dp[m][i] > dp[n][i]:
                dp[m][i] = dp[n][i]

print(min(dp[-1]))

Submission Info

Submission Time
Task A - Range Flip Find Route
User maspy
Language PyPy3 (2.4.0)
Score 400
Code Size 1001 Byte
Status AC
Exec Time 421 ms
Memory 66652 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 17
Set Name Test Cases
Sample example_00, example_01, example_02, example_03
All corner_00, corner_01, example_00, example_01, example_02, example_03, kuronuri_00, max_answer_00, max_answer_01, max_answer_02, max_random_00, max_random_01, max_random_02, max_random_03, one_path_00, one_path_01, one_path_02
Case Name Status Exec Time Memory
corner_00 AC 413 ms 66652 KB
corner_01 AC 398 ms 65884 KB
example_00 AC 185 ms 39920 KB
example_01 AC 182 ms 38384 KB
example_02 AC 202 ms 40816 KB
example_03 AC 204 ms 41072 KB
kuronuri_00 AC 406 ms 64860 KB
max_answer_00 AC 401 ms 64732 KB
max_answer_01 AC 402 ms 64860 KB
max_answer_02 AC 404 ms 65244 KB
max_random_00 AC 421 ms 65244 KB
max_random_01 AC 402 ms 64860 KB
max_random_02 AC 417 ms 65372 KB
max_random_03 AC 381 ms 62300 KB
one_path_00 AC 401 ms 64604 KB
one_path_01 AC 408 ms 64988 KB
one_path_02 AC 398 ms 65244 KB