#include #include #include #include #include int main() { int h, w; std::cin >> h >> w; auto source = std::vector(h); for (int i = 0; i < h; i++) std::cin >> source[i]; auto goal = std::vector(h); for (int i = 0; i < h; i++) std::cin >> goal[i]; constexpr int INFINITY = { 10'000'000 }; auto dist = std::vector(h, std::vector(w, INFINITY)); int a = 0; int b = 0; auto queue = std::vector>{}; for (int r = 0; r < h; r++) { for (int c = 0; c < w; c++) { if (goal[r][c] == '*') { queue.push_back({r, c}); dist[r][c] = 0; a += 1; } } } auto valid = [&](int r, int c) { if (!(0 <= r && r < h && 0 <= c && c < w)) return false; return goal[r][c] != 'X'; }; int queue_idx = 0; while (queue_idx < queue.size()) { auto [r, c] = queue[queue_idx++]; for (int dr = -1; dr <= 1; dr++) { for (int dc = -1; dc <= 1; dc++) { if (dr != 0 || dc != 0) { auto r1 = r + dr; auto c1 = c + dc; if (valid(r1, c1)) { if (dist[r1][c1] == INFINITY) { dist[r1][c1] = dist[r][c] + 1; queue.push_back({r1, c1}); } } } } } } // for (int i = 0; i != h; ++i) { // for (int j = 0; j != w; ++j) { // std::cerr << dist[i][j] << ' '; // } // std::cerr << '\n'; // } struct Node { bool was_prev; bool is_leaf; int dist; int r; int c; bool operator<(const Node &rhs) const { return std::tuple{dist, !was_prev, is_leaf, r, c} < std::tuple{rhs.dist, !rhs.was_prev, rhs.is_leaf, rhs.r, rhs.c}; } }; auto included = std::priority_queue{}; auto border = std::priority_queue{}; auto in_border = std::vector(h, std::vector(w)); auto in_shape = std::vector(h, std::vector(w)); int off = 0; auto delta = std::vector>{{-1, 0}, {0, 1}, {0, -1}, {1, 0}}; for (int r = 0; r < h; r++) { for (int c = 0; c < w; c++) { if (source[r][c] == '*') { in_shape[r][c] = true; b += 1; // std::cerr << "in shape: " << r << ' ' << c << '\n'; if (dist[r][c] != 0) { if (dist[r][c] == INFINITY) { std::cout << "NO\n"; std::exit(0); } int count_neighbours = 0; for (auto [dr, dc] : delta) { auto r1 = r + dr; auto c1 = c + dc; if (!valid(r1, c1)) continue; if (source[r][c] == '*') count_neighbours += 1; } included.push({false, count_neighbours == 1, dist[r][c], r, c}); off += 1; } } } } if (a != b) { std::cout << "NO\n"; // wot return 0; } for (int r = 0; r < h; r++) { for (int c = 0; c < w; c++) { if (source[r][c] == '*') { for (auto [dr, dc] : delta) { auto r1 = r + dr; auto c1 = c + dc; if (valid(r1, c1) && !in_border[r1][c1] && !in_shape[r1][c1]) { in_border[r1][c1] = true; // std::cerr << "in border: " << r1 << ' ' << c1 << '\n'; border.push({false, false, -dist[r1][c1], r1, c1}); } } } } } auto isleaf = [&](int rt, int ct) { int count_n = 0; for (auto [dr, dc] : delta) { auto r1 = rt + dr; auto c1 = ct + dc; if (!valid(r1, c1)) continue; if (in_shape[r1][c1]) count_n += 1; } return count_n == 1; }; auto moves = std::vector>{}; int prevr = -1; int prevc = -1; bool prevl = false; while (off > 0) { // std::cerr << included.size() << '\n'; // auto w = reinterpret_cast &>(included); // for (auto [a, b, c, d, e] : w) { // std::cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << '\n'; // } redof: auto [was_prev, is_leaf, dist1, rf, cf] = included.top(); included.pop(); if (!in_shape[rf][cf] || isleaf(rf, cf) != is_leaf) { goto redof; } redo: auto [aaaaa, bbbbb, dist2, rt, ct] = border.top(); border.pop(); if (!in_border[rt][ct]) goto redo; // std::cerr << dist1 << ' ' << dist2 << ' ' << r << ' ' << r1 << ' ' << c << ' ' << c1 << '\n'; moves.push_back({rf, cf, rt, ct}); in_shape[rf][cf] = false; in_shape[rt][ct] = true; in_border[rt][ct] = false; if (prevr != -1) { included.push({false, prevl, dist[prevr][prevc], prevr, prevc}); } if (dist[rt][ct] > 0) { prevr = rt; prevc = ct; prevl = isleaf(rt, ct); included.push({true, prevl, dist[rt][ct], rt, ct}); } else off -= 1; for (auto [dr, dc] : delta) { auto r1 = rf + dr; auto c1 = cf + dc; if (!valid(r1, c1)) continue; bool any = false; for (auto [dr1, dc1] : delta) { auto r2 = r1 + dr1; auto c2 = c1 + dc1; if (!valid(r2, c2)) continue; if (in_shape[r2][c1]) { any = true; break; } } if (in_shape[r1][c1]) any = false; in_border[r1][c1] = any; if (any) border.push({false, false, -dist[r1][c1], r1, c1}); if (in_shape[r1][c1]) included.push({false, isleaf(r1, c1), dist[r1][c1], r1, c1}); } for (auto [dr, dc] : delta) { auto r1 = rt + dr; auto c1 = ct + dc; if (!valid(r1, c1)) continue; bool any = false; for (auto [dr1, dc1] : delta) { auto r2 = r1 + dr1; auto c2 = c1 + dc1; if (!valid(r2, c2)) continue; if (in_shape[r2][c2]) { any = true; break; } } if (in_shape[r1][c1]) any = false; in_border[r1][c1] = any; if (any) { border.push({false, false, -dist[r1][c1], r1, c1}); } if (in_shape[r1][c1]) included.push({false, isleaf(r1, c1), dist[r1][c1], r1, c1}); } } std::cout << "YES\n" << moves.size() << "\n"; for (auto [r, c, r1, c1] : moves) { std::cout << r + 1 << ' ' << c + 1 << ' ' << r1 + 1 << ' ' << c1 + 1 << '\n'; } }