結果
問題 | No.2411 Reverse Directions |
ユーザー |
|
提出日時 | 2023-08-11 22:41:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,304 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 82,160 KB |
実行使用メモリ | 125,464 KB |
最終ジャッジ日時 | 2024-11-18 17:37:48 |
合計ジャッジ時間 | 6,446 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 16 WA * 13 |
ソースコード
import sys, time, random from collections import deque, Counter, defaultdict input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 63 - 1 mod = 998244353 h, w, K, l, r = mi() s = [input() for _ in range(h)] dist = [[inf, inf] * w for _ in range(h)] bef = [[None] * w for _ in range(h)] dist[0][0] = 0 bef[0][0] = (0, 0) q = deque() q.append((0, 0)) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] dz = 'UDLR' while q: nowi, nowj = q.popleft() for to in range(4): toi = nowi + dx[to] toj = nowj + dy[to] if 0 <= toi < h and 0 <= toj < w and s[toi][toj] == '.' and dist[toi][toj] > dist[nowi][nowj] + 1: dist[toi][toj] = dist[nowi][nowj] + 1 bef[toi][toj] = (nowi, nowj) q.append((toi, toj)) if dist[h - 1][w - 1] > K - (r - l + 1) or dist[h - 1][w - 1] % 2 != K % 2: print('No') else: root = [(h - 1, w - 1)] nowi, nowj = h - 1, w - 1 while True: toi, toj = bef[nowi][nowj] if toi == nowi and toj == nowj: break root.append((toi, toj)) nowi = toi nowj = toj root.reverse() x = [] for i in range(len(root) - 1): if root[i + 1][0] - root[i][0] == 1: x.append('D') elif root[i + 1][0] - root[i][0] == -1: x.append('U') elif root[i + 1][1] - root[i][1] == 1: x.append('R') else: x.append('L') x = deque(x) ans = [] nowi = 0 nowj = 0 while len(ans) < K: if l - 1 <= len(ans) <= r - 2 or not x: for k in range(4): toi = nowi + dx[k] toj = nowj + dy[k] to2i = nowi + dx[k^1] to2j = nowj + dy[k^2] if 0 <= toi < h and 0 <= toj < w and 0 <= to2i < h and 0 <= to2j < w and s[toi][toj] == '.' and s[to2i][to2j] == '.': ans.append(dz[k]) ans.append(dz[k^1]) break else: print('No') exit() else: ans.append(x.popleft()) nowi += dx[dz.index(ans[-1])] nowj += dy[dz.index(ans[-1])] print('Yes') print(''.join(ans))