結果
問題 | No.2411 Reverse Directions |
ユーザー |
![]() |
提出日時 | 2023-08-11 23:05:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 2,240 bytes |
コンパイル時間 | 255 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 122,180 KB |
最終ジャッジ日時 | 2024-11-18 18:23:12 |
合計ジャッジ時間 | 4,738 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
import sysinput = sys.stdin.readlinemove = [(1, 0), (0, 1), (-1, 0), (0, -1)]dirs = "DRUL"def bfs(si, sj):from collections import dequeINF = 10**18dist = [[INF] * W for _ in range(H)]prv = [[-1] * W for _ in range(H)]dist[si][sj] = 0que = deque([(si, sj)])while que:i, j = que.popleft()for k, (di, dj) in enumerate(move):ni, nj = i+di, j+djif 0 <= ni < H and 0 <= nj < W and dist[ni][nj] == INF and S[ni][nj] == '.':dist[ni][nj] = dist[i][j] + 1prv[ni][nj] = kque.append((ni, nj))return dist, prvdef out(si, sj, d):print("Yes")res = []i, j = si, sjwhile True:p = prvs[i][j]if p == -1:breakres.append(p)di, dj = move[p ^ 2]i += dij += djres = res[::-1]for k, (di, dj) in enumerate(move):ni, nj = si+di, sj+djif 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':for l in range(L-1-len(res)):res.append(k ^ ((l % 2)*2))breakfor k in range(R-L+1):res.append(d[k % 2])i, j = si, sjwhile True:p = prvt[i][j]if p == -1:breakres.append(p ^ 2)di, dj = move[p ^ 2]i += dij += djif S[H-2][W-1] == '.':for k in range(K-len(res)):res.append([2, 0][k % 2])else:for k in range(K-len(res)):res.append([3, 1][k % 2])print("".join(map(lambda k: dirs[k], res)))H, W, K, L, R = map(int, input().split())S = [input().rstrip() for _ in range(H)]if (H+W) % 2 != K % 2 or (R - L + 1) % 2 != 0:print("No")exit()dists, prvs = bfs(0, 0)distt, prvt = bfs(H-1, W-1)for i in range(H):for j in range(W):if (dists[i][j] - (L - 1)) % 2 == 0 and dists[i][j] <= L-1 and distt[i][j] <= K-R:# iif 0 < i < H-1 and S[i-1][j] == '.' and S[i+1][j] == '.':out(i, j, [0, 2])exit()# jif 0 < j < W-1 and S[i][j-1] == '.' and S[i][j+1] == '.':out(i, j, [1, 3])exit()print("No")