#include using namespace std; struct Seg { int r, c, d, n; }; struct Rect { int u, d, l, r; }; int H, W, tot, U, D, L, R; vector a; vector> ray; vector sum; vector used; const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1}; int num(int r, int c) { return r * W + c; } int row(int p) { return p / W; } int col(int p) { return p % W; } int direction(int x, int y) { int r = row(y) - row(x), c = col(y) - col(x); for (int d = 0; d < 4; ++d) if (r == dr[d] && c == dc[d]) return d; return -1; } vector border() { vector p; for (int c = L; c < R; ++c) p.push_back(num(U, c)); for (int r = U; r < D; ++r) p.push_back(num(r, R)); for (int c = R; c > L; --c) p.push_back(num(D, c)); for (int r = D; r > U; --r) p.push_back(num(r, L)); return p; } bool inside(Rect z, int r, int c) { return z.u <= r && r <= z.d && z.l <= c && c <= z.r; } int count(Rect z) { if (z.u > z.d || z.l > z.r) return 0; auto s = [&](int r, int c) { return sum[r * (W + 1) + c]; }; return s(z.d + 1, z.r + 1) - s(z.u, z.r + 1) - s(z.d + 1, z.l) + s(z.u, z.l); } // z の中を、st から turn 方向へ曲がり続けて貪欲にたどる。 bool spiral(Rect z, int st, int d, int turn, vector& v) { v.clear(); int r = row(st), c = col(st), got = 0; for (int first = 1;; first = 0, d = (d + turn + 4) % 4) { auto get = [&]() { int x = r + dr[d], y = c + dc[d]; if (!inside(z, x, y) || a[x][y] == '#') return 0; int n = d == 0 ? x - z.u + 1 : d == 1 ? z.r - y + 1 : d == 2 ? z.d - x + 1 : y - z.l + 1; n = min(n, ray[num(x, y)][d]); if (v.size() >= 3) { Seg q = v[v.size() - 3]; int qr = q.r + dr[q.d] * q.n; int qc = q.c + dc[q.d] * q.n; if ((d & 1) && min(q.r, qr) <= r && r <= max(q.r, qr)) { int e = (q.c - c) * dc[d]; if (!e) return -1; if (e > 0) n = min(n, e - 1); } if (!(d & 1) && min(q.c, qc) <= c && c <= max(q.c, qc)) { int e = (q.r - r) * dr[d]; if (!e) return -1; if (e > 0) n = min(n, e - 1); } } return n; }; int n = get(); if (first && n == 0) { d = (d + turn + 4) % 4; n = get(); } if (n < 0) return false; if (!n) break; if (v.size() >= 2 && n >= v[v.size() - 2].n) return false; v.push_back({r, c, d, n}); r += dr[d] * n; c += dc[d] * n; got += n; } return got == count(z); } // 外周が真の区間なら一度しか呼ばれないので、こちらはセル単位でよい。 void trace(int st, int d, int turn, int tag, int& cnt, vector& v) { int r = row(st), c = col(st); while (true) { int sr = r, sc = c, n = 0; while (true) { int x = r + dr[d], y = c + dc[d]; if (x < 0 || x >= H || y < 0 || y >= W || a[x][y] == '#' || used[num(x, y)] == tag) break; r = x; c = y; ++n; ++cnt; used[num(r, c)] = tag; } if (n) v.push_back({sr, sc, d, n}); d = (d + turn + 4) % 4; int x = r + dr[d], y = c + dc[d]; if (x < 0 || x >= H || y < 0 || y >= W || a[x][y] == '#' || used[num(x, y)] == tag) break; } } void add(vector>& v, int d, int n) { if (!n) return; if (!v.empty() && v.back().first == d) v.back().second += n; else v.push_back({d, n}); } void reverse_arm(vector>& run, const vector& v) { for (int i = (int)v.size() - 1; i >= 0; --i) add(run, v[i].d ^ 2, v[i].n); } void forward_arm(vector>& run, const vector& v) { for (auto s : v) add(run, s.d, s.n); } bool output(int start, const vector>& run) { int moves = 0; string cmd; for (int i = 0; i < (int)run.size(); ++i) { int d = run[i].first, n = run[i].second; if (i && d != (run[i - 1].first + 1) % 4) return false; moves += n; cmd += i ? 'R' : 'F'; cmd.append(n - 1, 'F'); } if (moves != tot - 1) return false; cout << row(start) + 1 << ' ' << col(start) + 1 << ' ' << "URDL"[run.empty() ? 0 : run[0].first] << '\n'; cout << moves << '\n' << cmd << '\n'; return true; } bool partial(const vector& arc, int order) { int tag = order + 1, cnt = arc.size(); for (int x : arc) used[x] = tag; vector x, y; int fd = direction(arc[0], arc[1]); int ld = direction(arc[arc.size() - 2], arc.back()); if (!order) { trace(arc[0], fd ^ 2, -1, tag, cnt, x); trace(arc.back(), ld, 1, tag, cnt, y); } else { trace(arc.back(), ld, 1, tag, cnt, y); trace(arc[0], fd ^ 2, -1, tag, cnt, x); } if (cnt != tot) return false; vector> run; reverse_arm(run, x); for (int i = 1; i < (int)arc.size(); ++i) add(run, direction(arc[i - 1], arc[i]), 1); forward_arm(run, y); int start = x.empty() ? arc[0] : num(x.back().r + dr[x.back().d] * x.back().n, x.back().c + dc[x.back().d] * x.back().n); return output(start, run); } bool full(const vector& p) { int n = p.size(), iu = U + 1, id = D - 1, il = L + 1, ir = R - 1; vector x, y; for (int k = 0; k < n; ++k) { int A = p[(k + 1) % n], B = p[k]; int ar = row(A), ac = col(A), br = row(B), bc = col(B); Rect xz, yz; if (ar == br) { int q = max(ac, bc); Rect l{iu, id, il, q - 1}, r{iu, id, q, ir}; tie(xz, yz) = ac >= q ? pair{r, l} : pair{l, r}; } else { int q = max(ar, br); Rect u{iu, q - 1, il, ir}, d{q, id, il, ir}; tie(xz, yz) = ar >= q ? pair{d, u} : pair{u, d}; } int fd = direction(A, p[(k + 2) % n]); int ld = direction(p[(k + n - 1) % n], B); if (!spiral(xz, A, fd ^ 2, -1, x) || !spiral(yz, B, ld, 1, y)) continue; vector> run; reverse_arm(run, x); for (int i = 1; i < n; ++i) add(run, direction(p[(k + i) % n], p[(k + i + 1) % n]), 1); forward_arm(run, y); int start = x.empty() ? A : num(x.back().r + dr[x.back().d] * x.back().n, x.back().c + dc[x.back().d] * x.back().n); if (output(start, run)) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> H >> W; a.resize(H); for (auto& s : a) cin >> s; U = H; D = -1; L = W; R = -1; for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) if (a[r][c] == '.') { ++tot; U = min(U, r); D = max(D, r); L = min(L, c); R = max(R, c); } if (U == D || L == R) { int len = U == D ? R - L + 1 : D - U + 1; if (len != tot) return cout << -1 << '\n', 0; vector> run; if (len > 1) run.push_back({U == D ? 1 : 2, len - 1}); output(num(U, L), run); return 0; } vector p = border(), arc; int n = p.size(), floors = 0, start = -1, blocks = 0; for (int i = 0; i < n; ++i) floors += a[row(p[i])][col(p[i])] == '.'; if (floors < n) { for (int i = 0; i < n; ++i) if (a[row(p[i])][col(p[i])] == '.' && a[row(p[(i + n - 1) % n])][col(p[(i + n - 1) % n])] == '#') start = i, ++blocks; if (blocks != 1) return cout << -1 << '\n', 0; for (int i = start; a[row(p[i])][col(p[i])] == '.'; i = (i + 1) % n) arc.push_back(p[i]); used.resize(H * W); if (arc.size() >= 2 && (partial(arc, 0) || partial(arc, 1))) return 0; return cout << -1 << '\n', 0; } ray.assign(H * W, {}); for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) if (a[r][c] == '.') ray[num(r,c)][0] = 1 + (r ? ray[num(r-1,c)][0] : 0); for (int r = 0; r < H; ++r) for (int c = W - 1; c >= 0; --c) if (a[r][c] == '.') ray[num(r,c)][1] = 1 + (c + 1 < W ? ray[num(r,c+1)][1] : 0); for (int r = H - 1; r >= 0; --r) for (int c = 0; c < W; ++c) if (a[r][c] == '.') ray[num(r,c)][2] = 1 + (r + 1 < H ? ray[num(r+1,c)][2] : 0); for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) if (a[r][c] == '.') ray[num(r,c)][3] = 1 + (c ? ray[num(r,c-1)][3] : 0); sum.assign((H + 1) * (W + 1), 0); for (int r = 0; r < H; ++r) for (int c = 0; c < W; ++c) sum[(r+1)*(W+1)+c+1] = (a[r][c] == '.') + sum[r*(W+1)+c+1] + sum[(r+1)*(W+1)+c] - sum[r*(W+1)+c]; if (!full(p)) cout << -1 << '\n'; }