INF = 1 << 29 DR = [1, 0, -1, 0] DC = [0, 1, 0, -1] h, w, k, l, r = read_line.split.map(&.to_i) if h - 1 + w - 1 > k || (h + w + k) % 2 != 0 || (r - l + 1) % 2 != 0 puts "No" exit end l -= 1 r -= 1 s = Array.new(h) { [true] + read_line.chars.map { |ch| ch == '#' } + [true] } s.unshift([true] * (w + 2)) s << [true] * (w + 2) dist0, prev0 = bfs(s, 1, 1) dist1, prev1 = bfs(s, h, w) py = -1 px = -1 1.upto(h) do |y| 1.upto(w) do |x| d0 = dist0[y][x] d1 = dist1[y][x] next if (l + d0) % 2 != 0 next if l < d0 next if (k - 1 - r + d1) % 2 != 0 next if k - 1 - r < d1 if !s[y - 1][x] && !s[y + 1][x] || !s[y][x - 1] && !s[y][x + 1] py = y px = x puts [py, px] end end end if py == -1 puts "No" exit end prefix = [] of Int32 cy = py cx = px while cy != 1 || cx != 1 dir = prev0[cy][cx] prefix << dir cy -= DR[dir] cx -= DC[dir] end prefix.reverse! suffix = [] of Int32 cy = py cx = px while cy != h || cx != w dir = prev1[cy][cx] suffix << (dir ^ 2) cy -= DR[dir] cx -= DC[dir] end ans = prefix if !s[py - 1][px] && !s[py + 1][px] ans += [0, 2] * ((k - prefix.size - suffix.size) // 2) else ans += [1, 3] * ((k - prefix.size - suffix.size) // 2) end ans += suffix puts ans.map { |d| "DRUL"[d] }.join def bfs(s, y, x) dist = Array.new(s.size) { Array.new(s[0].size, INF) } prev = Array.new(s.size) { Array.new(s[0].size, 5) } dist[y][x] = 0 q = [{y, x}] qi = 0 while qi < q.size cy, cx = q[qi] 4.times do |dir| ny = cy + DR[dir] nx = cx + DC[dir] if !s[ny][nx] && dist[ny][nx] == INF q << {ny, nx} dist[ny][nx] = dist[cy][cx] + 1 prev[ny][nx] = dir end end qi += 1 end return {dist, prev} end