#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int MaxN = 2e2 + 10; const int MOD = 1e9 + 7; const int INF = 1e9; char s[MaxN][MaxN]; int n, m, was[MaxN][MaxN]; pair < int, int > pred[MaxN][MaxN]; vector < pair < int, int > > all; void dfs(int x, int y) { if (s[x][y] == '*' || was[x][y] == 1) { return; } was[x][y] = 1; all.push_back(make_pair(x, y)); dfs(x + 1, y); dfs(x - 1, y); dfs(x, y - 1); dfs(x, y + 1); } int main() { // freopen("input.txt", "r", stdin); scanf("%d%d\n", &n, &m); for (int i = 1; i <= n; ++i) { gets(s[i] + 1); } pair < int, int > cap; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (s[i][j] == 'C') { cap = make_pair(i, j); } } } bool fnd = false; for (int i = 1; i <= n && !fnd; ++i) { for (int j = 1; j <= m && !fnd; ++j) { if (s[i][j] != '*') { dfs(i, j); fnd = true; } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (s[i][j] != '*') { assert (was[i][j] == 1); } } } all.erase(find(all.begin(), all.end(), cap)); string res; while (!all.empty()) { int where = rand() % (int)all.size(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { was[i][j] = 0; pred[i][j] = make_pair(-1, -1); } } queue < pair < int, int > > q; pair < int, int > st = all[where]; q.push(all[where]); was[q.front().first][q.front().second] = 1; while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for (int dx = -1; dx <= +1; ++dx) { for (int dy = -1; dy <= +1; ++dy) { if (abs(dx) + abs(dy) != 1) { continue; } int nx = x + dx, ny = y + dy; if (s[nx][ny] == '*' || was[nx][ny] == 1) { continue; } pred[nx][ny] = make_pair(x, y); was[nx][ny] = 1; q.push(make_pair(nx, ny)); } } } vector < pair < int, int > > pth; pair < int, int > fi = cap; while (fi != st) { pair < int, int > nxt = pred[fi.first][fi.second]; pth.push_back(make_pair(fi.first - nxt.first, fi.second - nxt.second)); fi = nxt; } reverse(pth.begin(), pth.end()); vector < pair < int, int > > nall; for (int it = 0; it < (int)all.size(); ++it) { pair < int, int > cur = all[it]; bool ok = false; for (int i = 0; i < (int)pth.size() && !ok; ++i) { int dx = pth[i].first, dy = pth[i].second; if (s[cur.first + dx][cur.second + dy] == '*') { continue; } cur.first += dx; cur.second += dy; if (s[cur.first][cur.second] == 'C') { ok = true; } } if (!ok) { nall.push_back(cur); } } for (int i = 0; i < (int)pth.size(); ++i) { if (pth[i].first == 1) { res += "D"; } else if (pth[i].second == 1) { res += "R"; } else if (pth[i].first == -1) { res += "U"; } else { res += "L"; } } all = nall; } cout << res << '\n'; return 0; }