結果
問題 | No.2411 Reverse Directions |
ユーザー |
![]() |
提出日時 | 2024-12-22 06:26:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 2,236 bytes |
コンパイル時間 | 433 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 132,864 KB |
最終ジャッジ日時 | 2024-12-22 06:26:24 |
合計ジャッジ時間 | 5,940 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
from collections import dequeH, W, K, L, R = map(int, input().split())S = [list(input()) for _ in range(H)]if (R-L+1)%2 == 1:exit(print("No"))def bfs(sh, sw):visited = [[-1]*W for _ in range(H)]visited[sh][sw] = 0que = deque()que.append((sh, sw))while que:h, w = que.popleft()for dh, dw in direction:nh, nw = h+dh, w+dwif 0<=nh<H and 0<=nw<W and visited[nh][nw] == -1 and S[nh][nw] == ".":visited[nh][nw] = visited[h][w]+1que.append((nh, nw))return visiteddef root(h, w, gh, gw, dist, B):ans = []while [h, w] != [gh, gw]:for i, (dh, dw) in enumerate(direction):nh, nw = h+dh, w+dwif 0<=nh<H and 0<=nw<W and dist[nh][nw] == dist[h][w]-1:ans.append(B[i])h, w = nh, nwbreakreturn ansdirection = [(-1,0),(0,1),(1,0),(0,-1)]distS = bfs(0, 0)distG = bfs(H-1, W-1)for i in range(H):for j in range(W):if distS[i][j] == -1 or distG[i][j] == -1:continueif distS[i][j]+distG[i][j] > K or (distS[i][j]+distG[i][j])%2 != K%2:continueif distS[i][j] >= L or distS[i][j]%2 == L%2:continuer = K-Rif distG[i][j] > r or distG[i][j]%2 != r%2:continueif 1 <= j < W-1 and S[i][j-1] == S[i][j+1] == ".":start = root(i, j, 0, 0, distS, ["D", "L", "U", "R"])[::-1]mid = []for _ in range((K-distS[i][j]-distG[i][j])//2):mid.append("L")mid.append("R")goal = root(i, j, H-1, W-1, distG, ["U", "R", "D", "L"])print("Yes")print("".join(start+mid+goal))exit()if 1 <= i < H-1 and S[i-1][j] == S[i+1][j] == ".":start = root(i, j, 0, 0, distS, ["D", "L", "U", "R"])[::-1]mid = []for _ in range((K-distS[i][j]-distG[i][j])//2):mid.append("U")mid.append("D")goal = root(i, j, H-1, W-1, distG, ["U", "R", "D", "L"])print("Yes")print("".join(start+mid+goal))exit()print("No")