using System.Text; static class Program { public static List Resize(this List list, int n, T var) { int count = list.Count; if (n < count) { list.RemoveRange(n, count - n); } else if (n > count) { if (n > list.Capacity) // Optimization list.Capacity = n; list.AddRange(Enumerable.Repeat(var, n - count)); } return list; } public static List Resize(this List lt, int n) => lt.Resize(n, default); public static List> Resize(this List> list, int n, int m, T var) { int count = list.Count; if (n < count) { list.RemoveRange(n, count - n); } else if (n > count) { for (int i = 0; i < n - count; i++) list.Add(new List().Resize(m, var)); } return list; } public static List> Resize(this List> lt, int n, int m) => lt.Resize(n, m, default); struct Vector2 { public int x, y; public Vector2(int _x, int _y) { x = _x; y = _y; } } class Graph { public int n; public List> E; public Graph(int _n) { n = _n; E = new List>(); E.Resize(n, 0); } public void add_edge(int u, int v, bool bi = false) { E[u].Add(v); if (bi) E[v].Add(u); } public List BFS(int s) { Queue q = new Queue(); List vit = new List(); vit.Resize(n, false); q.Enqueue(s); vit[s] = true; while (q.Count > 0) { int top = q.Dequeue(); foreach (int t in E[top]) { if (vit[t]) continue; vit[t] = true; q.Enqueue(t); } } return vit; } } class SCC : Graph { public int sccCount; public List> scc; public List group; private Stack stk; private List fin; private List dfsn; private int cnt; public SCC(int _n) : base(_n) { cnt = 0; fin = new List(); fin.Resize(n, false); scc = new List>(); scc.Resize(n, 0); group = new List(); group.Resize(n, -1); dfsn = new List(); dfsn.Resize(n, 0); stk = new Stack(); } private int dfs(int u) { dfsn[u] = ++cnt; stk.Push(u); int ret = dfsn[u]; foreach (int v in E[u]) { if (dfsn[v] == 0) ret = Math.Min(ret, dfs(v)); else if (!fin[v]) ret = Math.Min(ret, dfsn[v]); } if (ret == dfsn[u]) { List now = new List(); while (true) { int top = stk.Pop(); now.Add(top); fin[top] = true; group[top] = sccCount; if (top == u) break; } scc.Add(now); sccCount++; } return ret; } public void Create() { for (int i = 0; i < n; i++) if (dfsn[i] == 0) dfs(i); } public Graph Compress() { int sz = sccCount; Graph ans = new Graph(sz); for (int i = 0; i < n; i++) { foreach (int j in E[i]) { int u = group[i], v = group[j]; if (u != v) ans.add_edge(u, v); } } for (int i = 0; i < sz; i++) ans.E[i] = ans.E[i].Distinct().ToList(); return ans; } } class TwoSat : SCC { public int size; public TwoSat(int _n) : base(2 * _n) { size = _n; } private int inv(int x) { return x + size; } public void add_clause(int u, int v, bool arev = false, bool brev = false) { int f1 = arev ? inv(u) : u, t1 = brev ? v : inv(v); int f2 = brev ? inv(v) : v, t2 = arev ? u : inv(u); add_edge(f1, t1); add_edge(f2, t2); } public List calc() { Create(); bool ok = true; for (int i = 0; i < size; i++) if (group[i] == group[inv(i)]) ok = false; List ans = new List(); ans.Resize(size, -1); if (ok) for (int i = 0; i < size; i++) ans[i] = Convert.ToInt32(group[i] > group[inv(i)]); return ans; } } class TiltMaze { public int n, m; public List arr; private int idx; public TiltMaze(int _n, int _m) { n = _n; m = _m; idx = 0; arr = new List(); arr.Resize(n, ""); } public TiltMaze(int _n, int _m, List _arr) : this(_n, _m) { ReadMap(_arr); } private List> num; private List inum; private List star = new List(); public void ReadMap(List _arr) { num = new List>(); num.Resize(n, m); inum = new List(); inum.Resize(n * m + 1, new Vector2(0, 0)); arr = new List(_arr); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (arr[i][j] != '#') { num[i][j] = ++idx; inum[num[i][j]] = new Vector2(i, j); } if (arr[i][j] == 'O') { sx = i; sy = j; } else if (arr[i][j] == '*') star.Add(new Vector2(i, j)); } } private int sx, sy; private List>[] dp; private int[] dx = { 1, 0, -1, 0 }; private int[] dy = { 0, 1, 0, -1 }; private void FillDP() { dp = new List>[4]; for (int i = 0; i < 4; i++) { dp[i] = new List>(); dp[i].Resize(n, m); } int tn = n, tm = m; for (int k = 0; k < 4; k++) { for (int i = 0; i < tm; i++) { int u = tn - 1, v = i; if (k > 1) u = 0; if (k % 2 == 1) (u, v) = (v, u); if (num[u][v] > 0) dp[k][u][v] = num[u][v]; } List lt = new List(); for (int i = 0; i < tn - 1; i++) lt.Add(i); if (k < 2) lt.Reverse(); if (k > 1) for (int i = 0; i < lt.Count; i++) lt[i]++; foreach (int i in lt) { for (int j = 0; j < tm; j++) { int ni = i, nj = j; if (k % 2 == 1) (ni, nj) = (nj, ni); if (arr[ni][nj] != '#') { dp[k][ni][nj] = num[ni][nj]; if (dp[k][ni + dx[k]][nj + dy[k]] > 0) dp[k][ni][nj] = dp[k][ni + dx[k]][nj + dy[k]]; } } } (tn, tm) = (tm, tn); } } private SCC scc; private void ConstructSCC() { scc = new SCC(idx + 1); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (arr[i][j] == '#') continue; for (int k = 0; k < 4; k++) scc.add_edge(num[i][j], dp[k][i][j]); } scc.Create(); } private int GetSCCGroup(int g) => scc.group[g]; private int GetSCCGroup(int x, int y) => GetSCCGroup(num[x][y]); public List Calc() { FillDP(); ConstructSCC(); int sz = scc.sccCount; Graph compress = scc.Compress(); int st = GetSCCGroup(sx, sy); TwoSat ts = new TwoSat(sz); ts.add_clause(st, st); List> reach = new List>(); reach.Resize(sz, sz, false); for (int i = 0; i < sz; i++) reach[i] = new List(compress.BFS(i)); for (int i = 0; i < sz; i++) { if (!reach[st][i]) ts.add_clause(i, i, true, true); else { for (int j = 0; j < sz; j++) { if (!reach[st][j]) continue; if (!reach[i][j] && !reach[j][i]) ts.add_clause(i, j, true, true); } } } foreach (Vector2 vec in star) { int u = dp[0][vec.x][vec.y], v = dp[1][vec.x][vec.y]; ts.add_clause(GetSCCGroup(u), GetSCCGroup(v)); } return ts.calc(); } private char Dir(Vector2 from, Vector2 to) { List txt = new List() { 'U', 'R', 'D', 'L' }; int nx = from.x - to.x, ny = from.y - to.y; int tx = (nx == 0 ? 0 : nx / Math.Abs(nx)), ty = (ny == 0 ? 0 : ny / Math.Abs(ny)); for (int j = 0; j < 4; j++) if (tx == dx[j] && ty == dy[j]) return txt[j]; return ' '; } private string Routing(List poses) { List txt = new List() { 'U', 'R', 'D', 'L' }; string ans = ""; int n = poses.Count; for (int i = 1; i < n; i++) ans.Append(Dir(poses[i - 1], poses[i])); return ans; } public string Tracking(List ret) { int sz = ret.Count; List candidate = new List(); List chk = new List(); chk.Resize(sz, false); foreach (int i in ret) { if (ret[i] == 1) { candidate.Add(i); chk[i] = true; } } Graph compress = scc.Compress(); List ind = new List(); ind.Resize(sz, 0); for (int i = 0; i < sz; i++) { if (!chk[i]) continue; foreach (int j in compress.E[i]) if (chk[j]) ind[j]++; } List start = new List(), end = new List(), vit = new List(); start.Resize(n, false); end.Resize(n, false); vit.Resize(n, false); Queue q = new Queue(); q.Enqueue(scc.group[num[sx][sy]]); List ord = new List(); while (q.Count > 0) { int top = q.Dequeue(); ord.Add(top); foreach (int j in compress.E[top]) { if (!chk[j]) continue; if (--ind[j] == 0) q.Enqueue(j); } Queue que = new Queue(); foreach (int i in scc.scc[top]) { if (i == num[sx][sy]) start[i] = true; if (start[i]) que.Enqueue(i); } while (que.Count > 0) { int u = que.Dequeue(); foreach (int v in scc.E[u]) { if (vit[v]) continue; if (scc.group[u] == scc.group[v]) { vit[v] = true; que.Enqueue(v); } else if (chk[scc.group[v]]) start[v] = end[u] = true; } } } List lv = new List(); lv.Resize(sz, 0); for (int i = 0; i < ord.Count; i++) lv[ord[i]] = i; foreach (int i in scc.scc[ord[ord.Count - 1]]) end[i] = true; Dictionary dis = new Dictionary(); Dictionary path = new Dictionary(); foreach (int i in candidate) { void ShortestPath(int g) { Dictionary id = new Dictionary(); { int i = 0; foreach (int u in scc.scc[g]) id[u] = i++; } Dictionary road = new Dictionary(); int scnt = 0, n = scc.scc[g].Count; foreach (Vector2 vec in star) { List lt = new List(); if (chk[scc.group[dp[0][vec.x][vec.y]]]) lt.Add(new Vector2(dp[0][vec.x][vec.y], dp[2][vec.x][vec.y])); if (chk[scc.group[dp[1][vec.x][vec.y]]]) lt.Add(new Vector2(dp[1][vec.x][vec.y], dp[3][vec.x][vec.y])); if (lt.Count == 2) { if (lv[scc.group[lt[0].x]] > lv[scc.group[lt[1].x]]) (lt[0], lt[1]) = (lt[1], lt[0]); } if (scc.group[lt[0].x] == g) { road[lt[0]] = scnt; road[new Vector2(lt[0].y, lt[0].x)] = scnt; scnt++; } } foreach (int s in scc.scc[g]) { if (!start[s]) continue; List> dst = new List>(); List> route = new List>(); dst.Resize(n, 1< q = new Queue(); q.Enqueue(new Vector2(id[s], 0)); dst[id[s]][0] = 0; while (q.Count > 0) { Vector2 top = q.Dequeue(); int pos = top.x, state = top.y; foreach (int v in scc.E[pos]) { if (scc.group[v] != g) continue; int tst = state; Vector2 e = new Vector2(pos, id[v]); if (road.ContainsKey(e)) tst |= (1 << road[e]); if (dst[id[v]][tst] == -1) { dst[id[v]][tst] = dst[pos][state] + 1; q.Enqueue(new Vector2(id[v], tst)); route[id[v]][tst] = top; } } } foreach (int e in scc.scc[g]) { if (!end[e]) continue; dis[new Vector2(s, e)] = dst[id[e]][(1 << scnt) - 1]; List poses = new List(); int now = e, nstate = (1 << scnt) - 1; while (true) { if (now == s && nstate == 0) break; Vector2 prv = route[now][nstate]; poses.Add(inum[now]); now = prv.x; nstate = prv.y; } poses.Reverse(); path[new Vector2(s, e)] = Routing(poses); } } } ShortestPath(i); } List>[] rdp = new List>[2], id = new List>[2], back = new List>[2]; for (int i = 0; i < 2; i++) { rdp[i] = new List>(); rdp[i].Resize(ord.Count, 0); id[i] = new List>(); id[i].Resize(ord.Count, 0); back[i] = new List>(); back[i].Resize(ord.Count, 0); } for (int o = 0; o < ord.Count; o++) { int st = 0, et = 0; foreach (int i in scc.scc[ord[o]]) { if (start[i]) { rdp[0][o].Add(0x3f3f3f3f); id[0][o].Add(i); back[0][o].Add(0); } if (end[i]) { rdp[1][o].Add(0x3f3f3f3f); id[1][o].Add(i); back[1][o].Add(0); } } } rdp[0][0][0] = 0; for (int o = 0; o < ord.Count; o++) { int cnt = scc.scc[ord[o]].Count; if (o > 0) { for (int i = 0; i < cnt; i++) { if (!start[i]) continue; for (int j = 0; j < cnt; j++) { if (!end[j]) continue; int d = rdp[1][o - 1][j] + 1; if (rdp[0][o][i] > d) { rdp[0][o][i] = d; back[0][o][i] = j; } } } } for (int i = 0; i < cnt; i++) { if (!end[i]) continue; for (int j = 0; j < cnt; j++) { if (!start[j]) continue; int d = rdp[0][o][j] + dis[new Vector2(id[0][o][j], id[1][o][i])]; if (rdp[1][o][i] > d) { rdp[1][o][i] = d; back[1][o][i] = j; } } } } StringBuilder ans = new StringBuilder(); int now = 0; for (int o = ord.Count - 1; o >= 0; o--) { int e = id[1][o][now], t = back[1][o][now], s = id[0][o][t]; string str = path[new Vector2(s, e)]; str.Reverse(); ans.Append(str); if (o > 0) { now = back[0][o][t]; str.Append(Dir(inum[id[1][o - 1][now]], inum[s])); } } for (int i = 0; i < ans.Length; i++) { if (ans[i] == 'L') ans[i] = 'R'; else if (ans[i] == 'R') ans[i] = 'L'; else if (ans[i] == 'U') ans[i] = 'D'; else if (ans[i] == 'D') ans[i] = 'U'; } string temp = ans.ToString(); temp.Reverse(); return temp; } } static void Main(string[] args) { string[] txt = Console.ReadLine().Split(' '); int n = int.Parse(txt[0]), m = int.Parse(txt[1]); List arr = new List(); for (int i = 0; i < n; i++) using (StringReader reader = new StringReader(Console.ReadLine())) arr.Add(reader.ReadLine()); TiltMaze maze = new TiltMaze(n, m, arr); List ans = maze.Calc(); if (ans[0] == -1) Console.WriteLine("NO"); else Console.WriteLine("YES"); } }