#include using namespace std; // 迷路固有の構造は使わず、通る順番を DFS で全探索する。 // 未訪問部分の連結性と次数による一般的な Hamilton 路の枝刈りだけを行う。 int H, W, floor_count; vector grid_data; vector used; vector floor_cell; vector cell_color; vector path; vector floor_cells; vector> next_cell; vector bfs_queue; vector reached; unsigned int reach_stamp; int unused_color_count[2]; long long searched_nodes; long long node_limit; constexpr int DR[4] = {-1, 0, 1, 0}; constexpr int DC[4] = {0, 1, 0, -1}; constexpr char DIR_NAME[5] = "URDL"; int cell_id(int r, int c) { return r * W + c; } int row_of(int p) { return p / W; } int col_of(int p) { return p % W; } int move_to(int p, int direction) { int r = row_of(p) + DR[direction]; int c = col_of(p) + DC[direction]; if (r < 0 || r >= H || c < 0 || c >= W) return -1; return cell_id(r, c); } bool is_unused_floor(int p) { return p >= 0 && floor_cell[p] && !used[p]; } void visit(int p) { used[p] = 1; --unused_color_count[cell_color[p]]; } void unvisit(int p) { used[p] = 0; ++unused_color_count[cell_color[p]]; } // 現在地から次に使える辺を allowed_next に入れたとき、残りに // Hamilton 路が存在するための必要条件を確認する。 bool can_finish(int current, int direction, bool direction_fixed, int visited_count) { int remaining = floor_count - visited_count; if (remaining == 0) return true; // グリッドは二部グラフなので、残りの路でも白黒のマス数は交互になる。 int current_color = cell_color[current]; int color_count[2] = { unused_color_count[0] + (current_color == 0), unused_color_count[1] + (current_color == 1), }; if (remaining % 2 == 1) { if (color_count[0] != color_count[1]) return false; } else { if (color_count[current_color] != color_count[current_color ^ 1] + 1) return false; } array allowed_next{}; int allowed_count = 0; if (direction_fixed) { for (int next_direction : {direction, (direction + 1) % 4}) { int q = next_cell[current][next_direction]; if (is_unused_floor(q)) allowed_next[allowed_count++] = q; } } else { for (int next_direction = 0; next_direction < 4; ++next_direction) { int q = next_cell[current][next_direction]; if (is_unused_floor(q)) allowed_next[allowed_count++] = q; } } if (allowed_count == 0) return false; // 現在地を離れた後に戻ることはできないため、未訪問部分だけで連結である必要がある。 if (++reach_stamp == 0) { fill(reached.begin(), reached.end(), 0); ++reach_stamp; } int head = 0, tail = 0; bfs_queue[tail++] = allowed_next[0]; reached[allowed_next[0]] = reach_stamp; int degree_one = 0; while (head < tail) { int p = bfs_queue[head++]; int degree = 0; for (int d = 0; d < 4; ++d) { int q = next_cell[p][d]; if (is_unused_floor(q)) { ++degree; if (reached[q] != reach_stamp) { reached[q] = reach_stamp; bfs_queue[tail++] = q; } } } for (int i = 0; i < allowed_count; ++i) { if (allowed_next[i] == p) { ++degree; break; } } if (degree == 0) return false; if (degree == 1 && ++degree_one >= 2) return false; } if (tail != remaining) return false; return true; } enum class SearchResult { found, impossible, interrupted, }; SearchResult dfs(int current, int direction, int visited_count) { if (visited_count == floor_count) return SearchResult::found; if (++searched_nodes > node_limit) return SearchResult::interrupted; if (!can_finish(current, direction, true, visited_count)) return SearchResult::impossible; // 同じ方向へ進む部分を 1 区間として扱う。 // 「何マス直進してから右折するか」を長い方から全探索するので、 // 1 マスごとの F/R の DFS と探索範囲は同じである。 vector straight_cells; int p = current; while (true) { int q = next_cell[p][direction]; if (!is_unused_floor(q)) break; straight_cells.push_back(q); visit(q); path.push_back(q); p = q; } int right_direction = (direction + 1) % 4; bool interrupted = false; for (int straight_count = straight_cells.size(); straight_count >= 0; --straight_count) { int endpoint = straight_count == 0 ? current : straight_cells[straight_count - 1]; int count = visited_count + straight_count; if (count == floor_count) return SearchResult::found; int q = next_cell[endpoint][right_direction]; if (!interrupted && is_unused_floor(q)) { visit(q); path.push_back(q); SearchResult result = dfs(q, right_direction, count + 1); if (result == SearchResult::found) return SearchResult::found; if (result == SearchResult::interrupted) interrupted = true; path.pop_back(); unvisit(q); } if (straight_count > 0) { path.pop_back(); unvisit(straight_cells[straight_count - 1]); } } return interrupted ? SearchResult::interrupted : SearchResult::impossible; } SearchResult search_from(int start) { visit(start); path.clear(); path.push_back(start); if (!can_finish(start, 0, false, 1)) { unvisit(start); return SearchResult::impossible; } for (int direction = 0; direction < 4; ++direction) { int q = next_cell[start][direction]; if (!is_unused_floor(q)) continue; visit(q); path.push_back(q); SearchResult result = dfs(q, direction, 2); if (result == SearchResult::found) return SearchResult::found; path.pop_back(); unvisit(q); if (result == SearchResult::interrupted) { unvisit(start); return SearchResult::interrupted; } } unvisit(start); return SearchResult::impossible; } void print_answer() { if (floor_count == 1) { cout << row_of(path[0]) + 1 << ' ' << col_of(path[0]) + 1 << " U\n"; cout << "0\n\n"; return; } int initial_direction = -1; for (int d = 0; d < 4; ++d) { if (move_to(path[0], d) == path[1]) initial_direction = d; } string commands; commands.reserve(floor_count - 1); int direction = initial_direction; for (int i = 1; i < floor_count; ++i) { int next_direction = -1; for (int d = 0; d < 4; ++d) { if (move_to(path[i - 1], d) == path[i]) next_direction = d; } commands.push_back(next_direction == direction ? 'F' : 'R'); direction = next_direction; } cout << row_of(path[0]) + 1 << ' ' << col_of(path[0]) + 1 << ' ' << DIR_NAME[initial_direction] << '\n'; cout << commands.size() << '\n' << commands << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> H >> W; grid_data.resize(H); for (string &row : grid_data) cin >> row; floor_count = 0; int color_count[2] = {0, 0}; for (int r = 0; r < H; ++r) { for (int c = 0; c < W; ++c) { if (grid_data[r][c] == '.') { ++floor_count; ++color_count[(r + c) & 1]; floor_cells.push_back(cell_id(r, c)); } } } if (abs(color_count[0] - color_count[1]) > 1) { cout << -1 << '\n'; return 0; } used.assign(H * W, 0); floor_cell.assign(H * W, 0); cell_color.resize(H * W); for (int p = 0; p < H * W; ++p) { floor_cell[p] = grid_data[row_of(p)][col_of(p)] == '.'; cell_color[p] = (row_of(p) + col_of(p)) & 1; } next_cell.resize(H * W); for (int p = 0; p < H * W; ++p) { for (int d = 0; d < 4; ++d) next_cell[p][d] = move_to(p, d); } bfs_queue.resize(H * W); reached.assign(H * W, 0); unused_color_count[0] = color_count[0]; unused_color_count[1] = color_count[1]; path.reserve(floor_count); if (floor_count == 1) { path.push_back(floor_cells[0]); print_answer(); return 0; } // 一般の Hamilton 路でも必要な、入力全体に対する簡単な次数判定。 int degree_one = 0; for (int p : floor_cells) { int degree = 0; for (int d = 0; d < 4; ++d) { int q = next_cell[p][d]; if (q >= 0 && floor_cell[q]) ++degree; } if (degree == 0) { cout << -1 << '\n'; return 0; } if (degree == 1) ++degree_one; } if (degree_one > 2) { cout << -1 << '\n'; return 0; } vector starts = floor_cells; stable_sort(starts.begin(), starts.end(), [](int a, int b) { auto degree = [](int p) { int result = 0; for (int d = 0; d < 4; ++d) { int q = next_cell[p][d]; if (q >= 0 && floor_cell[q]) ++result; } return result; }; return degree(a) < degree(b); }); // 1 つの開始マスだけに長時間を使わないよう、探索ノード上限を // 段階的に増やす。解なしと証明できた開始マスは次回以降省く。 vector exhausted(starts.size(), 0); node_limit = 256; while (true) { bool all_exhausted = true; for (int i = 0; i < static_cast(starts.size()); ++i) { if (exhausted[i]) continue; searched_nodes = 0; SearchResult result = search_from(starts[i]); if (result == SearchResult::found) { #ifdef LOCAL cerr << "start=" << row_of(starts[i]) + 1 << ',' << col_of(starts[i]) + 1 << " limit=" << node_limit << " nodes=" << searched_nodes << '\n'; #endif print_answer(); return 0; } if (result == SearchResult::impossible) { exhausted[i] = 1; } else { all_exhausted = false; } } if (all_exhausted) break; if (node_limit <= numeric_limits::max() / 4) node_limit *= 4; else node_limit = numeric_limits::max(); } cout << -1 << '\n'; return 0; }