#include using namespace std; struct Key { unsigned long long mask; int state; bool operator==(const Key& other) const { return mask == other.mask && state == other.state; } }; struct KeyHash { size_t operator()(const Key& k) const { unsigned long long x = k.mask ^ (0x9e3779b97f4a7c15ULL * (unsigned long long)(k.state + 1)); x += 0x9e3779b97f4a7c15ULL; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL; x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL; x ^= x >> 31; return x; } }; int H, W, N; vector S; vector> cell; vector> nxt; vector used; const int dr[4] = {-1, 0, 1, 0}; const int dc[4] = {0, 1, 0, -1}; const char DIR[4] = {'U', 'R', 'D', 'L'}; string cur_ans, ans; int ans_start, ans_dir; bool use_mask; unsigned long long mask_now; unordered_set ng; // 現在地 cur と未訪問頂点だけで、 // 全頂点を通るパスが存在するための必要条件を確認 bool check(int cur, int cnt) { int rem = N - cnt + 1; if (rem == 1) return true; // 二部グラフの色数条件 int color[2] = {}; for (int v = 0; v < N; v++) { if (v != cur && used[v]) continue; auto [r, c] = cell[v]; color[(r + c) & 1]++; } int cc = (cell[cur].first + cell[cur].second) & 1; if (rem & 1) { if (color[cc] != color[cc ^ 1] + 1) return false; } else { if (color[0] != color[1]) return false; } // 残ったマスが全部連結か vector seen(N); queue q; seen[cur] = true; q.push(cur); int connected = 0; while (!q.empty()) { int v = q.front(); q.pop(); connected++; for (int d = 0; d < 4; d++) { int u = nxt[v][d]; if (u == -1 || seen[u]) continue; if (u != cur && used[u]) continue; seen[u] = true; q.push(u); } } if (connected != rem) return false; // 残ったグラフで次数1の頂点は、 // cur 以外には終点候補の1個まで int leaf = 0; for (int v = 0; v < N; v++) { if (v != cur && used[v]) continue; int deg = 0; for (int d = 0; d < 4; d++) { int u = nxt[v][d]; if (u == -1) continue; if (u == cur || !used[u]) deg++; } if (v == cur) { if (deg == 0) return false; } else { if (deg == 0) return false; if (deg == 1) { leaf++; if (leaf >= 2) { return false; } } } } return true; } bool dfs(int v, int dir, int cnt) { if (cnt == N) { return true; } if (use_mask) { Key key{mask_now, v * 4 + dir}; if (ng.find(key) != ng.end()) { return false; } } if (!check(v, cnt)) { if (use_mask) { ng.insert({mask_now, v * 4 + dir}); } return false; } // 0 = F : 直進 // 1 = R : 右折 for (int turn = 0; turn < 2; turn++) { int nd = (dir + turn) % 4; int u = nxt[v][nd]; if (u == -1 || used[u]) continue; used[u] = true; if (use_mask) { mask_now |= 1ULL << u; } cur_ans.push_back(turn == 0 ? 'F' : 'R'); if (dfs(u, nd, cnt + 1)) { return true; } cur_ans.pop_back(); if (use_mask) { mask_now ^= 1ULL << u; } used[u] = false; } if (use_mask) { ng.insert({mask_now, v * 4 + dir}); } 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 id(H, vector(W, -1)); for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (S[r][c] == '.') { id[r][c] = (int)cell.size(); cell.push_back({r, c}); } } } N = cell.size(); nxt.assign(N, {-1, -1, -1, -1}); for (int v = 0; v < N; v++) { auto [r, c] = cell[v]; 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; } nxt[v][d] = id[nr][nc]; } } // 床が1マスだけ if (N == 1) { auto [r, c] = cell[0]; cout << r + 1 << ' ' << c + 1 << " U\n"; cout << 0 << '\n'; cout << '\n'; return 0; } // 普通の Hamilton path としてすら無理なケースを先に弾く int color[2] = {}; vector leaf; for (int v = 0; v < N; v++) { auto [r, c] = cell[v]; color[(r + c) & 1]++; int deg = 0; for (int d = 0; d < 4; d++) { if (nxt[v][d] != -1) { deg++; } } if (deg == 0) { cout << -1 << '\n'; return 0; } if (deg == 1) { leaf.push_back(v); } } if (abs(color[0] - color[1]) > 1 || leaf.size() > 2) { cout << -1 << '\n'; return 0; } // 全床マスが連結か { vector seen(N); queue q; seen[0] = true; q.push(0); int cnt = 0; while (!q.empty()) { int v = q.front(); q.pop(); cnt++; for (int d = 0; d < 4; d++) { int u = nxt[v][d]; if (u == -1 || seen[u]) continue; seen[u] = true; q.push(u); } } if (cnt != N) { cout << -1 << '\n'; return 0; } } // Hamilton path の端点候補 vector starts; // 次数1が2個なら、この2頂点が必ず端点になる if (leaf.size() == 2) { starts = leaf; } else { starts.resize(N); iota(starts.begin(), starts.end(), 0); } // 64マス以下なら訪問集合をメモ化 use_mask = (N <= 64); used.assign(N, false); for (int s : starts) { // 床マス数が奇数なら、 // 始点・終点は市松模様で多数派側 if ((N & 1) && color[0] != color[1]) { auto [r, c] = cell[s]; int sc = (r + c) & 1; if (color[sc] < color[sc ^ 1]) { continue; } } for (int dir = 0; dir < 4; dir++) { fill(used.begin(), used.end(), false); used[s] = true; cur_ans.clear(); if (use_mask) { mask_now = 1ULL << s; ng.clear(); } if (dfs(s, dir, 1)) { ans_start = s; ans_dir = dir; ans = cur_ans; auto [r, c] = cell[s]; cout << r + 1 << ' ' << c + 1 << ' ' << DIR[dir] << '\n'; cout << ans.size() << '\n'; cout << ans << '\n'; return 0; } } } cout << -1 << '\n'; }