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 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 bfs_dist(sh, sw): dist = [[-1] * W for _ in range(H)] q = Queue() dist[sh][sw] = 0 q.put((sh, sw)) while not q.empty(): v = q.get() for d in range(4): nh = v[0] + DH[d] nw = v[1] + DW[d] if nh < 0 or nh >= H or nw < 0 or nw >= W: continue if dist[nh][nw] != -1: continue if Ss[nh][nw] == "#": continue dist[nh][nw] = dist[v[0]][v[1]] + 1 q.put((nh, nw)) 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((sh, sw)) while q and dist[gh][gw] == INF: v = q.get() for d in range(4): nh = v[0] + DH[d] nw = v[1] + DW[d] if nh < 0 or nh >= H or nw < 0 or nw >= W: continue if dist[nh][nw] != INF: continue if Ss[nh][nw] == "#": continue dist[nh][nw] = dist[v[0]][v[1]] + 1 prev[nh][nw] = "UDLR"[d] q.put((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) for h in range(H): for w in range(W): if 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 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 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(): global H, W, K, L, R, Ss H, W, K, L, R = map(int, input().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 = input().strip() assert len(s) == W for char in s: assert char == "." or char == "#" Ss.append(s) assert Ss[0][0] == "." and Ss[H - 1][W - 1] == "." fast() if __name__ == "__main__": main()