#include using namespace std; int H, W, N, r0, r1, c0, c1; vector G; vector> runlen; vector used; const int dr[4] = {-1, 0, 1, 0}; const int dc[4] = {0, 1, 0, -1}; inline int id(int r, int c) { return r * W + c; } inline int row(int p) { return p / W; } inline int col(int p) { return p % W; } inline int go(int p, int d) { int r = row(p) + dr[d], c = col(p) + dc[d]; return 0 <= r && r < H && 0 <= c && c < W ? id(r, c) : -1; } int dir(int a, int b) { int x = row(b) - row(a), y = col(b) - col(a); for (int d = 0; d < 4; d++) if (x == dr[d] && y == dc[d]) return d; return -1; } // 外接長方形の外周を時計回りに列挙する vector perimeter() { vector p; for (int c = c0; c < c1; c++) p.push_back(id(r0, c)); for (int r = r0; r < r1; r++) p.push_back(id(r, c1)); for (int c = c1; c > c0; c--) p.push_back(id(r1, c)); for (int r = r1; r > r0; r--) p.push_back(id(r, c0)); return p; } // turn=-1: 左折, turn=+1: 右折 vector trace(int st, int d, int turn, unsigned char tag, int &cnt) { vector ret; int p = st; while (true) { int q = go(p, d); if (q != -1 && G[row(q)][col(q)] == '.' && used[q] != tag) { used[q] = tag; ++cnt; ret.push_back(q); p = q; continue; } int nd = (d + turn + 4) % 4; q = go(p, nd); if (q != -1 && G[row(q)][col(q)] == '.' && used[q] != tag) { d = nd; used[q] = tag; ++cnt; ret.push_back(q); p = q; } else { break; } } return ret; } bool valid(const vector &p) { if ((int)p.size() != N) return false; fill(used.begin(), used.end(), 0); int last = -1; for (int i = 0; i < N; i++) { int x = p[i]; if (x < 0 || G[row(x)][col(x)] != '.' || used[x]) return false; used[x] = 1; if (i) { int d = dir(p[i - 1], x); if (d < 0 || (last != -1 && d != last && d != (last + 1) % 4)) return false; last = d; } } return true; } // 外周が真の部分区間 arc である場合 bool try_arc(const vector &arc, int order, vector &ans) { unsigned char tag = order + 1; int cnt = 0; for (int x : arc) { used[x] = tag; ++cnt; } int A = arc.front(), B = arc.back(); int first_dir = dir(arc[0], arc[1]); int last_dir = dir(arc[arc.size() - 2], arc.back()); vector pre, suf; if (order == 0) { pre = trace(A, (first_dir + 2) % 4, -1, tag, cnt); suf = trace(B, last_dir, +1, tag, cnt); } else { suf = trace(B, last_dir, +1, tag, cnt); pre = trace(A, (first_dir + 2) % 4, -1, tag, cnt); } if (cnt != N) return false; ans.clear(); ans.reserve(N); for (auto it = pre.rbegin(); it != pre.rend(); ++it) ans.push_back(*it); ans.insert(ans.end(), arc.begin(), arc.end()); ans.insert(ans.end(), suf.begin(), suf.end()); return valid(ans); } struct Rect { int u, d, l, r; }; struct Seg { int sr, sc, er, ec, dir, len; }; inline bool inside(const Rect &z, int r, int c) { return z.u <= r && r <= z.d && z.l <= c && c <= z.r; } // 現在位置から方向 d へ進める極大長。 // 過去の経路で当たり得るのは 3 区間前だけ。 int getlen(int r, int c, int d, const Rect &z, const vector &seg) { int x = r + dr[d], y = c + dc[d]; if (!inside(z, x, y) || G[x][y] == '#') return 0; int cap; if (d == 0) cap = x - z.u + 1; else if (d == 1) cap = z.r - y + 1; else if (d == 2) cap = z.d - x + 1; else cap = y - z.l + 1; int len = min(runlen[id(x, y)][d], cap); int j = seg.size(); if (j >= 3) { const Seg &old = seg[j - 3]; if (d & 1) { // 今回は横、old は縦 if (old.sc != old.ec) return -1; if (min(old.sr, old.er) <= r && r <= max(old.sr, old.er)) { int dist = (old.sc - c) * dc[d]; if (dist == 0) return -1; if (dist > 0) len = min(len, dist - 1); } } else { // 今回は縦、old は横 if (old.sr != old.er) return -1; if (min(old.sc, old.ec) <= c && c <= max(old.sc, old.ec)) { int dist = (old.sr - r) * dr[d]; if (dist == 0) return -1; if (dist > 0) len = min(len, dist - 1); } } } return len; } // 長方形 z 内の全床マスを、内向きスパイラルで被覆できるか bool arm(const Rect &z, int st, int heading, int turn, int need, vector &seg) { seg.clear(); int r = row(st), c = col(st); int d = heading, got = 0; bool first = true; while (true) { int len = getlen(r, c, d, z, seg); // 最初だけ、直進できなければ 1 回曲がってよい if (first && len == 0) { d = (d + turn + 4) % 4; len = getlen(r, c, d, z, seg); } first = false; if (len < 0) return false; if (len == 0) break; int j = seg.size(); // 内向きスパイラルの必要条件 if (j >= 2 && len >= seg[j - 2].len) return false; int nr = r + dr[d] * len; int nc = c + dc[d] * len; seg.push_back({r, c, nr, nc, d, len}); got += len; if (got > need) return false; r = nr; c = nc; d = (d + turn + 4) % 4; } return got == need; } void append_reverse(vector &ans, const vector &seg) { for (int i = (int)seg.size() - 1; i >= 0; i--) { int r = seg[i].er, c = seg[i].ec; int d = seg[i].dir; for (int k = 0; k < seg[i].len; k++) { ans.push_back(id(r, c)); r -= dr[d]; c -= dc[d]; } } } void append_forward(vector &ans, const vector &seg) { for (const Seg &s : seg) { int r = s.sr, c = s.sc; for (int k = 0; k < s.len; k++) { r += dr[s.dir]; c += dc[s.dir]; ans.push_back(id(r, c)); } } } // 外周全体が床の場合 bool solve_full(const vector &per, vector &ans) { int P = per.size(); int iu = r0 + 1, idn = r1 - 1; int il = c0 + 1, ir = c1 - 1; vector colsum(W + 1), rowsum(H + 1); int inner = 0; if (iu <= idn && il <= ir) { for (int r = iu; r <= idn; r++) { for (int c = il; c <= ir; c++) { if (G[r][c] == '.') { ++colsum[c + 1]; ++rowsum[r + 1]; ++inner; } } } } for (int c = 0; c < W; c++) colsum[c + 1] += colsum[c]; for (int r = 0; r < H; r++) rowsum[r + 1] += rowsum[r]; vector sa, sb; sa.reserve(H + W + 5); sb.reserve(H + W + 5); // per[cut] -> per[cut+1] を使わない辺とする for (int cut = 0; cut < P; cut++) { int A = per[(cut + 1) % P]; int B = per[cut]; int ar = row(A), ac = col(A); int br = row(B), bc = col(B); Rect RA, RB; int needA, needB; if (ar == br) { // 水平な切れ目。内側を左右に分割 int x = max(ac, bc); Rect L{iu, idn, il, x - 1}; Rect R{iu, idn, x, ir}; int cntL = (iu <= idn && il <= x - 1) ? colsum[x] - colsum[il] : 0; int cntR = inner - cntL; if (ac >= x) { RA = R; RB = L; needA = cntR; needB = cntL; } else { RA = L; RB = R; needA = cntL; needB = cntR; } } else { // 垂直な切れ目。内側を上下に分割 int x = max(ar, br); Rect U{iu, x - 1, il, ir}; Rect D{x, idn, il, ir}; int cntU = (il <= ir && iu <= x - 1) ? rowsum[x] - rowsum[iu] : 0; int cntD = inner - cntU; if (ar >= x) { RA = D; RB = U; needA = cntD; needB = cntU; } else { RA = U; RB = D; needA = cntU; needB = cntD; } } int first_dir = dir(A, per[(cut + 2) % P]); int last_dir = dir(per[(cut - 1 + P) % P], B); if (!arm(RA, A, (first_dir + 2) % 4, -1, needA, sa)) continue; if (!arm(RB, B, last_dir, +1, needB, sb)) continue; ans.clear(); ans.reserve(N); append_reverse(ans, sa); for (int j = 0; j < P; j++) ans.push_back(per[(cut + 1 + j) % P]); append_forward(ans, sb); if (valid(ans)) return true; } return false; } void output(const vector &path) { int initial_dir = 0; string command; command.reserve(max(0, N - 1)); if (N >= 2) { initial_dir = dir(path[0], path[1]); int current = initial_dir; for (int i = 1; i < N; i++) { int nd = dir(path[i - 1], path[i]); if (nd == current) command.push_back('F'); else command.push_back('R'); current = nd; } } static const char name[] = "URDL"; cout << row(path[0]) + 1 << ' ' << col(path[0]) + 1 << ' ' << name[initial_dir] << '\n'; cout << command.size() << '\n'; cout << command << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> H >> W; G.resize(H); for (string &s : G) cin >> s; r0 = H; r1 = -1; c0 = W; c1 = -1; N = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (G[r][c] == '.') { ++N; r0 = min(r0, r); r1 = max(r1, r); c0 = min(c0, c); c1 = max(c1, c); } } } used.assign(H * W, 0); vector answer; // 全床マスが 1 行上 if (r0 == r1) { if (N != c1 - c0 + 1) { cout << -1 << '\n'; return 0; } for (int c = c0; c <= c1; c++) answer.push_back(id(r0, c)); output(answer); return 0; } // 全床マスが 1 列上 if (c0 == c1) { if (N != r1 - r0 + 1) { cout << -1 << '\n'; return 0; } for (int r = r0; r <= r1; r++) answer.push_back(id(r, c0)); output(answer); return 0; } vector per = perimeter(); int P = per.size(); vector on(P); int boundary_count = 0; for (int i = 0; i < P; i++) { on[i] = (G[row(per[i])][col(per[i])] == '.'); boundary_count += on[i]; } // 外周が全部ではない if (boundary_count < P) { int start = -1, starts = 0; for (int i = 0; i < P; i++) { if (on[i] && !on[(i + P - 1) % P]) { start = i; ++starts; } } if (starts != 1) { cout << -1 << '\n'; return 0; } vector arc; for (int i = start; on[i]; i = (i + 1) % P) arc.push_back(per[i]); if ((int)arc.size() != boundary_count || arc.size() < 2) { cout << -1 << '\n'; return 0; } if (try_arc(arc, 0, answer) || try_arc(arc, 1, answer)) { output(answer); return 0; } cout << -1 << '\n'; return 0; } // 4 方向の連続床マス数 runlen.assign(H * W, {}); for (int r = 0; r < H; r++) for (int c = 0; c < W; c++) if (G[r][c] == '.') runlen[id(r, c)][0] = 1 + (r ? runlen[id(r - 1, c)][0] : 0); for (int r = 0; r < H; r++) for (int c = W - 1; c >= 0; c--) if (G[r][c] == '.') runlen[id(r, c)][1] = 1 + (c + 1 < W ? runlen[id(r, c + 1)][1] : 0); for (int r = H - 1; r >= 0; r--) for (int c = 0; c < W; c++) if (G[r][c] == '.') runlen[id(r, c)][2] = 1 + (r + 1 < H ? runlen[id(r + 1, c)][2] : 0); for (int r = 0; r < H; r++) for (int c = 0; c < W; c++) if (G[r][c] == '.') runlen[id(r, c)][3] = 1 + (c ? runlen[id(r, c - 1)][3] : 0); if (solve_full(per, answer)) { output(answer); return 0; } cout << -1 << '\n'; }