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 |
|
|
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 |