#include using namespace std; const int MAXN = 21; #define FOR(i,a,b) for (int (i)=(a);(i)<(b);(i)++) #define REP(i,n) FOR(i,0,n) char grid[MAXN][MAXN]; int n, m; int taken[MAXN][MAXN], vis[MAXN][MAXN]; pair parent[MAXN][MAXN]; vector > persons; int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '*'; } void print(vector > path) { cerr << "path " << endl; for (auto x : path) cerr << x.first << " " << x.second << endl; cerr << endl; } int check(string command) { int totalReached = 0; int good = true; REP(i, n) REP(j, m) if (grid[i][j] == '.') { int x = i, y = j; int ok = false; REP(it, command.size()) { char ch = command[it]; int dx = 0, dy = 0; if (ch == 'U') dx--; if (ch == 'D') dx++; if (ch == 'L') dy--; if (ch == 'R') dy++; int nx = x + dx; int ny = y + dy; if (valid(nx, ny)) { x = nx; y = ny; } if (grid[x][y] == 'C') ok = true; } if (ok) totalReached++; else good = false; } cerr << "totalReached " << totalReached << endl; return good; } // Find a path between (begx, begy) to (endx, endy) in the grid graph using bfs. vector > findPath(int begx, int begy, int endx, int endy) { memset(vis, 0, sizeof(vis)); REP(i, n) REP(j, m) parent[i][j] = {0, 0}; queue > Q; Q.push({begx, begy}); vis[begx][begy] = true; parent[begx][begy] = {begx, begy}; int reachableEnd = false; while (!Q.empty()) { auto from = Q.front(); Q.pop(); int x = from.first; int y = from.second; if (x == endx && y == endy) { reachableEnd = true; } FOR(dx, -1, 2) FOR(dy, -1, 2) if (abs(dx) + abs(dy) == 1) { int nx = x + dx; int ny = y + dy; if (valid(nx, ny) && !vis[nx][ny]) { vis[nx][ny] = true; assert(nx - x == 0 || ny - y == 0); parent[nx][ny] = {x, y}; Q.push({nx, ny}); } } } assert(reachableEnd); vector > path; int startx = endx, starty = endy; while (startx != begx || starty != begy) { path.push_back({startx, starty}); int nstartx = parent[startx][starty].first; int nstarty = parent[startx][starty].second; startx = nstartx; starty = nstarty; } path.push_back({startx, starty}); reverse(path.begin(), path.end()); return path; } string command = ""; // Move all the people parrallely along this path. void movePath(vector > path) { FOR(i, 1, path.size()) { int dx = path[i].first - path[i - 1].first; int dy = path[i].second - path[i - 1].second; char dir = 'U'; if (dx == 0) { if (dy == 1) dir = 'R'; else { dir = 'L'; assert(dy == -1); } } else if (dy == 0) { if (dx == 1) dir = 'D'; else { dir = 'U'; assert(dx == -1); } } else { print(path); assert(false); } command += dir; for (auto &per : persons) { int nx = get<0> (per) + dx; int ny = get<1> (per) + dy; if (valid(nx, ny)) { per = make_tuple(nx, ny, get<2> (per)); } } } } int main() { scanf("%d %d", &n, &m); REP(i, n) scanf("%s", grid[i]); int cnt = 0, endx = 0, endy = 0; REP(i, n) REP(j, m) { if (grid[i][j] == '.') persons.push_back(make_tuple(i, j, cnt++)); if (grid[i][j] == 'C') { endx = i; endy = j; } } REP(c, cnt) { int begx, begy; for (auto per : persons) if (get<2> (per) == c) { begx = get<0> (per); begy = get<1> (per); } auto path = findPath(begx, begy, endx, endy); movePath(path); } cout << command << endl; assert(check(command)); return 0; }