#include using namespace std; struct Seg { int d; int r1, c1, r2, c2; int len; }; int H, W; vector S; // 各マスから U,R,D,L に、壁に当たるまで何歩進めるか vector> go_len; // 各候補のシミュレーションで使い回す vector buf; const int dr[4] = {-1, 0, 1, 0}; const int dc[4] = {0, 1, 0, -1}; const char DCH[4] = {'U', 'R', 'D', 'L'}; const int INF = 1e9; // (r,c) から d 方向に進んだとき、 // segment s のマスに初めてぶつかるまでの距離。 // ぶつからないなら INF。 int hitDist(int r, int c, int d, const Seg& s) { int rlo = min(s.r1, s.r2); int rhi = max(s.r1, s.r2); int clo = min(s.c1, s.c2); int chi = max(s.c1, s.c2); if (d == 0) { // U if (s.r1 == s.r2) { if (clo <= c && c <= chi && s.r1 < r) { return r - s.r1; } } else if (s.c1 == c) { int rr = min(rhi, r - 1); if (rlo <= rr) { return r - rr; } } } else if (d == 1) { // R if (s.c1 == s.c2) { if (rlo <= r && r <= rhi && s.c1 > c) { return s.c1 - c; } } else if (s.r1 == r) { int cc = max(clo, c + 1); if (cc <= chi) { return cc - c; } } } else if (d == 2) { // D if (s.r1 == s.r2) { if (clo <= c && c <= chi && s.r1 > r) { return s.r1 - r; } } else if (s.c1 == c) { int rr = max(rlo, r + 1); if (rr <= rhi) { return rr - r; } } } else { // L if (s.c1 == s.c2) { if (rlo <= r && r <= rhi && s.c1 < c) { return c - s.c1; } } else if (s.r1 == r) { int cc = min(chi, c - 1); if (clo <= cc) { return c - cc; } } } return INF; } // sign = +1: // 直進できる限り直進 → 右折 // // sign = -1: // 直進できる限り直進 → 左折 // // 左折版が完成した場合は最後に経路を逆転する。 bool simulate( int sr, int sc, int first_dir, int sign, int N, int& seg_cnt ) { int r = sr; int c = sc; int d = first_dir; int cnt = 1; int m = 0; // 同じ向きに曲がり続ける単純な螺旋では // 線分数は O(H+W)。 int seg_limit = 4 * (H + W) + 20; while (cnt < N && m < seg_limit) { int L = go_len[r * W + c][d]; // 螺旋では、次に衝突し得る既訪問部分は // 直近5本の線分のどれか。 for (int j = max(0, m - 5); j < m; j++) { int k = hitDist(r, c, d, buf[j]); if (k <= L) { L = k - 1; } } if (L <= 0) { return false; } int nr = r + dr[d] * L; int nc = c + dc[d] * L; buf[m++] = { d, r, c, nr, nc, L }; cnt += L; if (cnt > N) { return false; } r = nr; c = nc; if (cnt == N) { seg_cnt = m; return true; } d = (d + sign + 4) % 4; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> H >> W; S.resize(H); for (auto& s : S) { cin >> s; } vector floor_cells; int N = 0; int color[2] = {}; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (S[r][c] == '.') { floor_cells.push_back(r * W + c); N++; color[(r + c) & 1]++; } } } // 床が1マスだけ if (N == 1) { int v = floor_cells[0]; cout << v / W + 1 << ' ' << v % W + 1 << " U\n"; cout << 0 << '\n'; cout << '\n'; return 0; } // 普通の Hamilton path としても必要な条件 if (abs(color[0] - color[1]) > 1) { cout << -1 << '\n'; return 0; } int leaves = 0; for (int v : floor_cells) { int r = v / W; int c = v % W; int deg = 0; for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; if (0 <= nr && nr < H && 0 <= nc && nc < W && S[nr][nc] == '.') { deg++; } } if (deg == 0) { cout << -1 << '\n'; return 0; } if (deg == 1) { leaves++; } } if (leaves > 2) { cout << -1 << '\n'; return 0; } // 連結判定 { vector seen(H * W, false); queue q; q.push(floor_cells[0]); seen[floor_cells[0]] = true; int cnt = 0; while (!q.empty()) { int v = q.front(); q.pop(); cnt++; int r = v / W; int c = v % W; for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; if (nr < 0 || nr >= H || nc < 0 || nc >= W) { continue; } int u = nr * W + nc; if (S[nr][nc] == '.' && !seen[u]) { seen[u] = true; q.push(u); } } } if (cnt != N) { cout << -1 << '\n'; return 0; } } // ----------------------------------------- // 壁まで何歩直進できるか前計算 // ----------------------------------------- go_len.assign(H * W, {0, 0, 0, 0}); // U, L for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (S[r][c] == '#') { continue; } int v = r * W + c; if (r > 0 && S[r - 1][c] == '.') { go_len[v][0] = go_len[(r - 1) * W + c][0] + 1; } if (c > 0 && S[r][c - 1] == '.') { go_len[v][3] = go_len[r * W + c - 1][3] + 1; } } } // D, R for (int r = H - 1; r >= 0; r--) { for (int c = W - 1; c >= 0; c--) { if (S[r][c] == '#') { continue; } int v = r * W + c; if (r + 1 < H && S[r + 1][c] == '.') { go_len[v][2] = go_len[(r + 1) * W + c][2] + 1; } if (c + 1 < W && S[r][c + 1] == '.') { go_len[v][1] = go_len[r * W + c + 1][1] + 1; } } } buf.resize(4 * (H + W) + 25); vector answer; int ans_sign = 0; // N が奇数なら始点・終点は市松模様の多数派色 int need_color = -1; if (N & 1) { need_color = (color[0] > color[1] ? 0 : 1); } // ----------------------------------------- // 開始マス × 最初の方向 × 回転方向を全探索 // ----------------------------------------- for (int sign : {1, -1}) { for (int v : floor_cells) { int sr = v / W; int sc = v % W; if (need_color != -1 && ((sr + sc) & 1) != need_color) { continue; } for (int d = 0; d < 4; d++) { // 最初の実移動を F にしてよい。 // // 本来最初が R だったとしても、 // 初期方向をその1つ右にしておけば // 同じ経路を F から開始できる。 if (go_len[v][d] == 0) { continue; } int m = 0; if (simulate( sr, sc, d, sign, N, m )) { answer.assign( buf.begin(), buf.begin() + m ); ans_sign = sign; goto FOUND; } } } } cout << -1 << '\n'; return 0; FOUND: vector out; if (ans_sign == 1) { // 最初から右折 spiral out = answer; } else { // 左折 spiral を逆向きにすると // 右折 spiral になる for (int i = (int)answer.size() - 1; i >= 0; i--) { Seg s = answer[i]; out.push_back({ (s.d + 2) % 4, s.r2, s.c2, s.r1, s.c1, s.len }); } } int sr = out[0].r1; int sc = out[0].c1; int sd = out[0].d; string X; X.reserve(N - 1); for (int i = 0; i < (int)out.size(); i++) { if (i == 0) { X.append(out[i].len, 'F'); } else { // 新しい線分へ移る最初の1歩だけ R X.push_back('R'); // 残りは直進 X.append(out[i].len - 1, 'F'); } } cout << sr + 1 << ' ' << sc + 1 << ' ' << DCH[sd] << '\n'; cout << X.size() << '\n'; cout << X << '\n'; }