結果
| 問題 | No.2411 Reverse Directions |
| ユーザー |
 hari64
|
| 提出日時 | 2023-07-19 21:48:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,558 bytes |
| コンパイル時間 | 440 ms |
| コンパイル使用メモリ | 82,404 KB |
| 実行使用メモリ | 273,268 KB |
| 最終ジャッジ日時 | 2024-10-09 18:44:43 |
| 合計ジャッジ時間 | 4,456 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 66 ms
75,816 KB |
| testcase_01 | AC | 66 ms
69,096 KB |
| testcase_02 | AC | 65 ms
69,644 KB |
| testcase_03 | AC | 64 ms
68,800 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
ソースコード
import sys
import time
from queue import Queue
DH = [-1, 1, 0, 0]
DW = [0, 0, -1, 1]
INF = 1001001001
H = -1
W = -1
K = -1
L = -1
R = -1
Ss = None
def simulateMove(T):
assert len(T) <= K
nowX, nowY = 0, 0
for move in T:
if move == "U":
nowY -= 1
elif move == "D":
nowY += 1
elif move == "L":
nowX -= 1
elif move == "R":
nowX += 1
else:
assert False
if nowX < 0 or nowX >= W or nowY < 0 or nowY >= H:
return (-1, -1)
if not Ss[nowY][nowX]:
return (-1, -1)
assert Ss[nowY][nowX]
return (nowX, nowY)
def isValidMovement(T):
assert len(T) == K
res = simulateMove(T)
nowX, nowY = res
if nowX == -1 and nowY == -1:
return False
return nowX == W - 1 and nowY == H - 1
def isValidAnswer(T):
if not isValidMovement(T):
return False
partialyReversed = list(T)
for i in range(L, R + 1):
if partialyReversed[i] == "U":
partialyReversed[i] = "D"
elif partialyReversed[i] == "D":
partialyReversed[i] = "U"
elif partialyReversed[i] == "L":
partialyReversed[i] = "R"
elif partialyReversed[i] == "R":
partialyReversed[i] = "L"
else:
assert False
return isValidMovement("".join(partialyReversed))
def toIdx(h, w):
return h * W + w
def toPos(idx):
return (idx // W, idx % W)
def bfs_dist(sh, sw):
dist = [-1 for _ in range(H * W)]
q = Queue()
dist[toIdx(sh, sw)] = 0
q.put(toIdx(sh, sw))
while not q.empty():
v = q.get()
h, w = toPos(v)
for d in range(4):
nh = h + DH[d]
nw = w + DW[d]
if nh < 0 or nh >= H or nw < 0 or nw >= W:
continue
nv = toIdx(nh, nw)
if dist[nv] != -1:
continue
if not Ss[nh][nw]:
continue
dist[nv] = dist[v] + 1
q.put(nv)
dist = [[dist[toIdx(h, w)] for w in range(W)] for h in range(H)]
return dist
def findPath(sh, sw, gh, gw):
dist = [[INF] * W for _ in range(H)]
prev = [["X"] * W for _ in range(H)]
q = Queue()
assert Ss[sh][sw]
dist[sh][sw] = 0
q.put(toIdx(sh, sw))
while q and dist[gh][gw] == INF:
v = q.get()
h, w = toPos(v)
for d in range(4):
nh = h + DH[d]
nw = w + DW[d]
if nh < 0 or nh >= H or nw < 0 or nw >= W:
continue
if dist[nh][nw] != INF:
continue
if not Ss[nh][nw]:
continue
dist[nh][nw] = dist[h][w] + 1
prev[nh][nw] = "UDLR"[d]
q.put(toIdx(nh, nw))
assert dist[gh][gw] != INF
nowH, nowW = gh, gw
path = ""
while prev[nowH][nowW] != "X":
p = prev[nowH][nowW]
path += p
if p == "U":
nowH += 1
elif p == "D":
nowH -= 1
elif p == "L":
nowW += 1
elif p == "R":
nowW -= 1
else:
assert False
return path[::-1]
def fast():
if L == 0 or R == K - 1:
print("No")
return
if (R - L + 1) % 2 == 1:
print("No")
return
distFromStart = bfs_dist(0, 0)
distFromGoal = bfs_dist(H - 1, W - 1)
print(time.time(), file=sys.stderr)
for h in range(H):
for w in range(W):
if not Ss[h][w]:
continue
if distFromStart[h][w] == -1:
continue
if distFromGoal[h][w] == -1:
continue
if (K - (distFromStart[h][w] + distFromGoal[h][w])) % 2 == 1:
continue
if distFromStart[h][w] > L:
continue
if distFromGoal[h][w] > K - 1 - R:
continue
for d in range(4):
nh1 = h + DH[d]
nw1 = w + DW[d]
if nh1 < 0 or nh1 >= H or nw1 < 0 or nw1 >= W:
continue
if not Ss[nh1][nw1]:
continue
nh2 = h + DH[d ^ 1]
nw2 = w + DW[d ^ 1]
if nh2 < 0 or nh2 >= H or nw2 < 0 or nw2 >= W:
continue
if not Ss[nh2][nw2]:
continue
path1 = findPath(0, 0, h, w)
path3 = findPath(h, w, H - 1, W - 1)
path2 = ""
for _ in range((K - (distFromStart[h][w] + distFromGoal[h][w])) // 2):
path2 += "UDLR"[d] + "DURL"[d]
answer = path1 + path2 + path3
if isValidAnswer(answer):
print("Yes")
print(answer)
return
print("No")
return
def main():
print(time.time(), file=sys.stderr)
global H, W, K, L, R, Ss
H, W, K, L, R = map(int, sys.stdin.readline().strip().split())
assert 3 <= H <= 500
assert 3 <= W <= 500
assert 4 <= K <= 500000
assert 1 <= L <= R <= K
L -= 1
R -= 1
Ss = []
for i in range(H):
s = sys.stdin.readline().strip()
assert len(s) == W
for char in s:
assert char == "." or char == "#"
Ss.append([char == "." for char in s])
assert Ss[0][0] and Ss[H - 1][W - 1]
print(time.time(), file=sys.stderr)
fast()
print(time.time(), file=sys.stderr)
if __name__ == "__main__":
main()