結果
| 問題 | No.3504 Insert Maze |
| コンテスト | |
| ユーザー |
 ,
|
| 提出日時 | 2026-04-19 02:20:59 |
| 言語 | Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,659 bytes |
| 記録 | |
| コンパイル時間 | 528 ms |
| コンパイル使用メモリ | 20,700 KB |
| 実行使用メモリ | 133,484 KB |
| 最終ジャッジ日時 | 2026-04-19 02:22:32 |
| 合計ジャッジ時間 | 25,066 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 WA * 9 TLE * 2 -- * 46 |
ソースコード
import sys
from collections import deque
def solve():
data = sys.stdin.buffer.read().split()
idx = 0
H = int(data[idx]); idx+=1
W = int(data[idx]); idx+=1
# Store grid as flat bytearray for speed
grid = []
for i in range(H):
grid.append(data[idx]); idx+=1
# grid[i][j] accessed as grid[i][j]
WALL = ord('#')
INF = 10**9
# 0 insertions BFS
dist = [INF] * (H*W)
if grid[0][0] != WALL:
dist[0] = 0
q = deque([0])
while q:
pos = q.popleft()
i,j = divmod(pos, W)
d = dist[pos]
for ni,nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
if 0<=ni<H and 0<=nj<W:
npos = ni*W+nj
if dist[npos]==INF and grid[ni][nj]!=WALL:
dist[npos] = d+1
q.append(npos)
d0 = dist[(H-1)*W+(W-1)]
best = d0
# For 1-insertion check, we need 4 restricted BFS.
# Optimize: store vis as flat array of bools.
def row_bfs_top():
# vis[i*W+j] = reachable from (0,0) in rows 0..i
vis = bytearray(H*W)
in_q = bytearray(H*W)
pending = [[] for _ in range(H)]
if grid[0][0] != WALL:
in_q[0] = 1
pending[0].append(0)
for row in range(H):
q2 = deque(pending[row])
while q2:
pos = q2.popleft()
if vis[pos]: continue
vis[pos] = 1
i,j = divmod(pos, W)
for ni,nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
if 0<=ni<H and 0<=nj<W:
npos = ni*W+nj
if not in_q[npos] and grid[ni][nj]!=WALL:
in_q[npos] = 1
if ni <= row:
q2.append(npos)
elif ni == row+1:
pending[row+1].append(npos)
return vis
def row_bfs_bot():
vis = bytearray(H*W)
in_q = bytearray(H*W)
pending = [[] for _ in range(H)]
start = (H-1)*W+(W-1)
if grid[H-1][W-1] != WALL:
in_q[start] = 1
pending[H-1].append(start)
for row in range(H-1,-1,-1):
q2 = deque(pending[row])
while q2:
pos = q2.popleft()
if vis[pos]: continue
vis[pos] = 1
i,j = divmod(pos, W)
for ni,nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
if 0<=ni<H and 0<=nj<W:
npos = ni*W+nj
if not in_q[npos] and grid[ni][nj]!=WALL:
in_q[npos] = 1
if ni >= row:
q2.append(npos)
elif ni == row-1:
pending[row-1].append(npos)
return vis
def col_bfs_left():
vis = bytearray(H*W)
in_q = bytearray(H*W)
pending = [[] for _ in range(W)]
if grid[0][0] != WALL:
in_q[0] = 1
pending[0].append(0)
for col in range(W):
q2 = deque(pending[col])
while q2:
pos = q2.popleft()
if vis[pos]: continue
vis[pos] = 1
i,j = divmod(pos, W)
for ni,nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
if 0<=ni<H and 0<=nj<W:
npos = ni*W+nj
if not in_q[npos] and grid[ni][nj]!=WALL:
in_q[npos] = 1
if nj <= col:
q2.append(npos)
elif nj == col+1:
pending[col+1].append(npos)
return vis
def col_bfs_right():
vis = bytearray(H*W)
in_q = bytearray(H*W)
pending = [[] for _ in range(W)]
start = (H-1)*W+(W-1)
if grid[H-1][W-1] != WALL:
in_q[start] = 1
pending[W-1].append(start)
for col in range(W-1,-1,-1):
q2 = deque(pending[col])
while q2:
pos = q2.popleft()
if vis[pos]: continue
vis[pos] = 1
i,j = divmod(pos, W)
for ni,nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
if 0<=ni<H and 0<=nj<W:
npos = ni*W+nj
if not in_q[npos] and grid[ni][nj]!=WALL:
in_q[npos] = 1
if nj >= col:
q2.append(npos)
elif nj == col-1:
pending[col-1].append(npos)
return vis
vis_top = row_bfs_top()
vis_bot = row_bfs_bot()
# Check row insertions
one_ins = False
for g in range(H-1):
top_row = vis_top[g*W:(g+1)*W]
bot_row = vis_bot[(g+1)*W:(g+2)*W]
if any(top_row) and any(bot_row):
one_ins = True
break
if not one_ins:
vis_left = col_bfs_left()
vis_right = col_bfs_right()
for g in range(W-1):
# col g in vis_left, col g+1 in vis_right
left_col = vis_left[g::W] # stride slice: cells (0,g),(1,g),...,(H-1,g)
right_col = vis_right[(g+1)::W]
if any(left_col) and any(right_col):
one_ins = True
break
if one_ins:
best = min(best, H+W-1)
best = min(best, H+W)
print(best)
solve()