ソースコード 拡げる

Copy
```import sys

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]))```

#### 提出情報

提出日時 2020-03-21 22:56:23+0900 A - Range Flip Find Route maspy PyPy3 (2.4.0) 400 1001 Byte AC 421 ms 66652 KB

#### ジャッジ結果

セット名 Sample All

 AC × 4
 AC × 17
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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