結果
| 問題 | No.3504 Insert Maze |
| コンテスト | |
| ユーザー |
 Nattt
|
| 提出日時 | 2026-04-18 00:01:52 |
| 言語 | Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,407 bytes |
| 記録 | |
| コンパイル時間 | 534 ms |
| コンパイル使用メモリ | 20,824 KB |
| 実行使用メモリ | 82,124 KB |
| 最終ジャッジ日時 | 2026-04-18 00:03:29 |
| 合計ジャッジ時間 | 22,296 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 WA * 3 TLE * 2 -- * 57 |
ソースコード
import sys
def solve():
input_data = sys.stdin.read().split()
if not input_data:
return
H = int(input_data[0])
W = int(input_data[1])
grid = input_data[2:]
N = H * W
empty = bytearray(N)
for r in range(H):
row = grid[r]
idx = r * W
for c in range(W):
if row[c] != '#':
empty[idx + c] = 1
dist = [-1] * (3 * N)
dist[0] = 0
Q = [[], [], []]
Q[0].append(0)
target = N - 1
if target == 0:
print(0)
return
d = 0
N_offset = N
N2_offset = 2 * N
while True:
idx_mod = d % 3
curr_q = Q[idx_mod]
if not curr_q:
if not Q[(d+1)%3] and not Q[(d+2)%3]:
break
d += 1
continue
q1 = Q[(d+1)%3]
q2 = Q[(d+2)%3]
app1 = q1.append
app2 = q2.append
d_plus_1 = d + 1
d_plus_2 = d + 2
for u in curr_q:
if dist[u] < d:
continue
if u == target:
print(d)
return
if u < N:
r, c = divmod(u, W)
if c > 0:
v = u - 1
if empty[v] and (dist[v] == -1 or d_plus_1 < dist[v]):
dist[v] = d_plus_1; app1(v)
if c < W - 1:
v = u + 1
if empty[v] and (dist[v] == -1 or d_plus_1 < dist[v]):
dist[v] = d_plus_1; app1(v)
if r > 0:
v = u - W
if empty[v] and (dist[v] == -1 or d_plus_1 < dist[v]):
dist[v] = d_plus_1; app1(v)
if r < H - 1:
v = u + W
if empty[v] and (dist[v] == -1 or d_plus_1 < dist[v]):
dist[v] = d_plus_1; app1(v)
if r < H - 1:
v = N_offset + u
if dist[v] == -1 or d_plus_1 < dist[v]:
dist[v] = d_plus_1; app1(v)
if r > 0:
v = N_offset + u - W
if dist[v] == -1 or d_plus_1 < dist[v]:
dist[v] = d_plus_1; app1(v)
if c < W - 1:
v = N2_offset + u
if dist[v] == -1 or d_plus_1 < dist[v]:
dist[v] = d_plus_1; app1(v)
if c > 0:
v = N2_offset + u - 1
if dist[v] == -1 or d_plus_1 < dist[v]:
dist[v] = d_plus_1; app1(v)
elif u < N2_offset:
rem = u - N_offset
r, c = divmod(rem, W)
v = rem
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
v = rem + W
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
if c > 0:
v = u - 1
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
if c < W - 1:
v = u + 1
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
if c < W - 1:
v = N2_offset + rem
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
v = N2_offset + rem + W
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
if c > 0:
v = N2_offset + rem - 1
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
v = N2_offset + rem + W - 1
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
else:
rem = u - N2_offset
r, c = divmod(rem, W)
v = rem
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
v = rem + 1
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
if r > 0:
v = u - W
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
if r < H - 1:
v = u + W
if dist[v] == -1 or d_plus_1 < dist[v]: dist[v] = d_plus_1; app1(v)
if r < H - 1:
v = N_offset + rem
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
v = N_offset + rem + 1
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
if r > 0:
v = N_offset + rem - W
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
v = N_offset + rem - W + 1
if dist[v] == -1 or d_plus_2 < dist[v]: dist[v] = d_plus_2; app2(v)
curr_q.clear()
d += 1
print(-1)
if __name__ == '__main__':
solve()