#include using namespace std; // 部分点 2 // 外周全体が床なら、使わない外周辺を 1 本決めることで内部を 2 長方形に分割できる。 // 各候補について 2 本の渦を 1 マスずつ実際に辿るため、計算量は O(HW(H+W))。 int H, W, floor_count; int top_row, bottom_row, left_col, right_col; vector grid_data; vector used; constexpr int DR[4] = {-1, 0, 1, 0}; constexpr int DC[4] = {0, 1, 0, -1}; constexpr char DIR_NAME[5] = "URDL"; struct Rect { int top, bottom, left, right; }; 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); } int direction_of(int from, int to) { for (int d = 0; d < 4; ++d) { if (move_to(from, d) == to) return d; } return -1; } bool is_floor(int p) { return p >= 0 && grid_data[row_of(p)][col_of(p)] == '.'; } bool inside(const Rect &rect, int p) { if (p < 0) return false; int r = row_of(p), c = col_of(p); return rect.top <= r && r <= rect.bottom && rect.left <= c && c <= rect.right; } vector bounding_perimeter() { vector result; for (int c = left_col; c < right_col; ++c) result.push_back(cell_id(top_row, c)); for (int r = top_row; r < bottom_row; ++r) result.push_back(cell_id(r, right_col)); for (int c = right_col; c > left_col; --c) result.push_back(cell_id(bottom_row, c)); for (int r = bottom_row; r > top_row; --r) result.push_back(cell_id(r, left_col)); return result; } vector trace_spiral(int start, int direction, int turn, const Rect *rect) { vector result; int current = start; while (true) { int next = move_to(current, direction); bool can_go = is_floor(next) && !used[next] && (rect == nullptr || inside(*rect, next)); if (!can_go) { int next_direction = (direction + turn + 4) % 4; next = move_to(current, next_direction); can_go = is_floor(next) && !used[next] && (rect == nullptr || inside(*rect, next)); if (!can_go) break; direction = next_direction; } used[next] = 1; result.push_back(next); current = next; } return result; } bool valid_path(const vector &path) { if (static_cast(path.size()) != floor_count) return false; fill(used.begin(), used.end(), 0); int previous_direction = -1; for (int i = 0; i < floor_count; ++i) { int p = path[i]; if (!is_floor(p) || used[p]) return false; used[p] = 1; if (i > 0) { int direction = direction_of(path[i - 1], p); if (direction < 0) return false; if (previous_direction >= 0 && direction != previous_direction && direction != (previous_direction + 1) % 4) { return false; } previous_direction = direction; } } return true; } bool try_boundary_arc(const vector &arc, int order, vector &answer) { fill(used.begin(), used.end(), 0); for (int p : arc) used[p] = 1; int first_direction = direction_of(arc[0], arc[1]); int last_direction = direction_of(arc[arc.size() - 2], arc.back()); vector prefix, suffix; if (order == 0) { prefix = trace_spiral(arc.front(), (first_direction + 2) % 4, -1, nullptr); suffix = trace_spiral(arc.back(), last_direction, +1, nullptr); } else { suffix = trace_spiral(arc.back(), last_direction, +1, nullptr); prefix = trace_spiral(arc.front(), (first_direction + 2) % 4, -1, nullptr); } if (prefix.size() + arc.size() + suffix.size() != static_cast(floor_count)) { return false; } answer.clear(); for (auto it = prefix.rbegin(); it != prefix.rend(); ++it) answer.push_back(*it); answer.insert(answer.end(), arc.begin(), arc.end()); answer.insert(answer.end(), suffix.begin(), suffix.end()); return valid_path(answer); } bool solve_full_perimeter(const vector &perimeter, vector &answer) { int perimeter_size = perimeter.size(); int inner_top = top_row + 1; int inner_bottom = bottom_row - 1; int inner_left = left_col + 1; int inner_right = right_col - 1; // perimeter[cut] -> perimeter[cut+1] を使わない外周辺とする。 for (int cut = 0; cut < perimeter_size; ++cut) { int a = perimeter[(cut + 1) % perimeter_size]; int b = perimeter[cut]; int ar = row_of(a), ac = col_of(a); int br = row_of(b), bc = col_of(b); Rect rect_a, rect_b; if (ar == br) { int split = max(ac, bc); Rect left{inner_top, inner_bottom, inner_left, split - 1}; Rect right{inner_top, inner_bottom, split, inner_right}; if (ac >= split) { rect_a = right; rect_b = left; } else { rect_a = left; rect_b = right; } } else { int split = max(ar, br); Rect upper{inner_top, split - 1, inner_left, inner_right}; Rect lower{split, inner_bottom, inner_left, inner_right}; if (ar >= split) { rect_a = lower; rect_b = upper; } else { rect_a = upper; rect_b = lower; } } fill(used.begin(), used.end(), 0); for (int p : perimeter) used[p] = 1; int first_direction = direction_of(a, perimeter[(cut + 2) % perimeter_size]); int last_direction = direction_of( perimeter[(cut - 1 + perimeter_size) % perimeter_size], b); vector prefix = trace_spiral( a, (first_direction + 2) % 4, -1, &rect_a); vector suffix = trace_spiral(b, last_direction, +1, &rect_b); if (prefix.size() + perimeter.size() + suffix.size() != static_cast(floor_count)) { continue; } answer.clear(); for (auto it = prefix.rbegin(); it != prefix.rend(); ++it) answer.push_back(*it); for (int i = 0; i < perimeter_size; ++i) answer.push_back(perimeter[(cut + 1 + i) % perimeter_size]); answer.insert(answer.end(), suffix.begin(), suffix.end()); if (valid_path(answer)) return true; } return false; } void print_answer(const vector &path) { int initial_direction = 0; if (floor_count >= 2) initial_direction = direction_of(path[0], path[1]); string commands; commands.reserve(max(0, floor_count - 1)); int direction = initial_direction; for (int i = 1; i < floor_count; ++i) { int next_direction = direction_of(path[i - 1], path[i]); 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; top_row = H; bottom_row = -1; left_col = W; right_col = -1; floor_count = 0; for (int r = 0; r < H; ++r) { for (int c = 0; c < W; ++c) { if (grid_data[r][c] == '.') { ++floor_count; top_row = min(top_row, r); bottom_row = max(bottom_row, r); left_col = min(left_col, c); right_col = max(right_col, c); } } } used.assign(H * W, 0); vector answer; if (top_row == bottom_row) { if (floor_count != right_col - left_col + 1) { cout << -1 << '\n'; return 0; } for (int c = left_col; c <= right_col; ++c) answer.push_back(cell_id(top_row, c)); print_answer(answer); return 0; } if (left_col == right_col) { if (floor_count != bottom_row - top_row + 1) { cout << -1 << '\n'; return 0; } for (int r = top_row; r <= bottom_row; ++r) answer.push_back(cell_id(r, left_col)); print_answer(answer); return 0; } vector perimeter = bounding_perimeter(); vector on_perimeter(perimeter.size(), 0); int perimeter_floor_count = 0; for (int i = 0; i < static_cast(perimeter.size()); ++i) { on_perimeter[i] = is_floor(perimeter[i]); perimeter_floor_count += on_perimeter[i]; } if (perimeter_floor_count < static_cast(perimeter.size())) { int start = -1; int intervals = 0; for (int i = 0; i < static_cast(perimeter.size()); ++i) { int previous = (i - 1 + perimeter.size()) % perimeter.size(); if (on_perimeter[i] && !on_perimeter[previous]) { start = i; ++intervals; } } if (intervals != 1) { cout << -1 << '\n'; return 0; } vector arc; for (int i = start; on_perimeter[i]; i = (i + 1) % perimeter.size()) arc.push_back(perimeter[i]); if (arc.size() < 2 || static_cast(arc.size()) != perimeter_floor_count || (!try_boundary_arc(arc, 0, answer) && !try_boundary_arc(arc, 1, answer))) { cout << -1 << '\n'; return 0; } print_answer(answer); return 0; } if (solve_full_perimeter(perimeter, answer)) { print_answer(answer); } else { cout << -1 << '\n'; } return 0; }