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
Exec Time 421 ms
Memory 66652 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_00, example_01, example_02, example_03
All 400 / 400 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 413 ms 66652 KB
corner_01 398 ms 65884 KB
example_00 185 ms 39920 KB
example_01 182 ms 38384 KB
example_02 202 ms 40816 KB
example_03 204 ms 41072 KB
kuronuri_00 406 ms 64860 KB
max_answer_00 401 ms 64732 KB
max_answer_01 402 ms 64860 KB
max_answer_02 404 ms 65244 KB
max_random_00 421 ms 65244 KB
max_random_01 402 ms 64860 KB
max_random_02 417 ms 65372 KB
max_random_03 381 ms 62300 KB
one_path_00 401 ms 64604 KB
one_path_01 408 ms 64988 KB
one_path_02 398 ms 65244 KB