#include using namespace std; struct Solver { int h, w, cells, floors; vector grid; vector seen; int stamp = 0; const int dr[4] = {-1, 0, 1, 0}; const int dc[4] = {0, 1, 0, -1}; const string dir_char = "URDL"; bool is_floor(int r, int c) const { return 0 <= r && r < h && 0 <= c && c < w && grid[r][c] == '.'; } bool try_start(int start, int initial_direction, bool print_answer) { ++stamp; int position = start; int direction = initial_direction; int visited = 1; seen[position] = stamp; string commands; if (print_answer) commands.reserve(floors - 1); while (visited < floors) { int r = position / w, c = position % w; bool moved = false; for (int turn = 0; turn <= 1; ++turn) { int next_direction = (direction + turn) & 3; int nr = r + dr[next_direction], nc = c + dc[next_direction]; if (!is_floor(nr, nc)) continue; int next = nr * w + nc; if (seen[next] == stamp) continue; position = next; direction = next_direction; seen[position] = stamp; ++visited; if (print_answer) commands.push_back(turn == 0 ? 'F' : 'R'); moved = true; break; } if (!moved) break; } if (visited != floors) return false; if (print_answer) { cout << start / w + 1 << ' ' << start % w + 1 << ' ' << dir_char[initial_direction] << '\n'; cout << commands.size() << '\n'; cout << commands << '\n'; } return true; } bool basic_impossibility() const { int first = -1; int leaves = 0; for (int r = 0; r < h; ++r) { for (int c = 0; c < w; ++c) { if (grid[r][c] == '#') continue; if (first == -1) first = r * w + c; int degree = 0; for (int d = 0; d < 4; ++d) degree += is_floor(r + dr[d], c + dc[d]); leaves += degree == 1; } } if (leaves >= 3) return true; vector reached(cells, 0); queue que; que.push(first); reached[first] = 1; int count = 0; while (!que.empty()) { int id = que.front(); que.pop(); ++count; int r = id / w, c = id % w; for (int d = 0; d < 4; ++d) { int nr = r + dr[d], nc = c + dc[d]; if (!is_floor(nr, nc)) continue; int next = nr * w + nc; if (!reached[next]) { reached[next] = 1; que.push(next); } } } return count != floors; } vector make_candidates(int walls) const { vector added(cells, 0); vector result; auto add = [&](int r, int c) { if (!is_floor(r, c)) return; int id = r * w + c; if (!added[id]) { added[id] = 1; result.push_back(id); } }; if ((cells <= 50000 && walls > 2) || min(h, w) <= 5) { for (int id = 0; id < cells; ++id) { if (grid[id / w][id % w] == '.') add(id / w, id % w); } return result; } for (int r = 0; r < h; ++r) { for (int c = 0; c < w; ++c) { if (r <= 1 || r >= h - 2 || c <= 1 || c >= w - 2) add(r, c); } } for (int r = 0; r < h; ++r) { for (int c = 0; c < w; ++c) { if (grid[r][c] != '#') continue; for (int nr = max(0, r - 2); nr <= min(h - 1, r + 2); ++nr) { for (int nc = max(0, c - 2); nc <= min(w - 1, c + 2); ++nc) { add(nr, nc); } } } } if (walls > 2) { for (int r = 0; r < h; ++r) { for (int c = 0; c < w; ++c) { if (grid[r][c] != '.') continue; int degree = 0; for (int d = 0; d < 4; ++d) degree += is_floor(r + dr[d], c + dc[d]); if (degree <= 2) add(r, c); } } } return result; } void run() { cells = h * w; floors = 0; int walls = 0; for (const string& row : grid) { floors += count(row.begin(), row.end(), '.'); walls += count(row.begin(), row.end(), '#'); } if (floors == 1) { for (int r = 0; r < h; ++r) for (int c = 0; c < w; ++c) { if (grid[r][c] == '.') { cout << r + 1 << ' ' << c + 1 << " U\n0\n\n"; return; } } } if (basic_impossibility()) { cout << -1 << '\n'; return; } seen.assign(cells, 0); vector candidates = make_candidates(walls); for (int start : candidates) { for (int direction = 0; direction < 4; ++direction) { if (try_start(start, direction, false)) { try_start(start, direction, true); return; } } } cout << -1 << '\n'; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); Solver solver; if (!(cin >> solver.h >> solver.w)) return 0; solver.grid.resize(solver.h); for (string& row : solver.grid) cin >> row; solver.run(); return 0; }