#include using namespace std; #define tsolve int t; cin >> t; while (t--) solve #define all(x) ::begin(x), ::end(x) #define sz(x) (ll)::size(x) using ll = long long; using ld = long double; using pll = pair; ll r, c; vector> o, s, t; vector ordered(vector> f, ll x, ll y) { vector res; vector> vis(r, vector(c, false)); vector search; search.push_back({ x, y }); vis[x][y] = true; while (!search.empty()) { auto [x, y] = search.back(); search.pop_back(); res.push_back({ x, y }); for (auto [dx, dy] : vector{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }) { if (x + dx < 0 || x + dx >= r) continue; if (y + dy < 0 || y + dy >= c) continue; if (!f[x + dx][y + dy]) continue; if (vis[x + dx][y + dy]) continue; vis[x + dx][y + dy] = true; search.push_back({ x + dx, y + dy }); } } return res; } void solve_intersecting(ll x, ll y) { vector sp = ordered(s, x, y); vector tp = ordered(t, x, y); reverse(all(tp)); vector> moves; while (!sp.empty() && !tp.empty()) { auto [sx, sy] = sp.back(); sp.pop_back(); auto [tx, ty] = tp.back(); tp.pop_back(); if (t[sx][sy]) { tp.push_back({ tx, ty }); continue; } if (s[tx][ty]) { sp.push_back({ sx, sy }); continue; } moves.push_back({{ sx, sy }, { tx, ty }}); } cout << "YES\n"; cout << ssize(moves) << '\n'; for (auto [ms, mt] : moves) { cout << (ms.first + 1) << ' ' << (ms.second + 1) << ' ' << (mt.first + 1) << ' ' << (mt.second + 1) << '\n'; } } vector find_path() { vector> par(r, vector(c)); vector> vis(r, vector(c, false)); vector search; for (ll i = 0; i < r; ++i) { for (ll j = 0; j < c; ++j) { if (s[i][j]) { search.push_back({ i, j }); vis[i][j] = true; } } } while (!search.empty()) { auto [x, y] = search.back(); search.pop_back(); if (t[x][y]) { vector res; while (!s[x][y]) { res.push_back({ x, y }); tie(x, y) = par[x][y]; } res.push_back({ x, y }); reverse(all(res)); return res; } for (auto [dx, dy] : vector{ { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } }) { if (x + dx < 0 || x + dx >= r) continue; if (y + dy < 0 || y + dy >= c) continue; if (o[x + dx][y + dy]) continue; if (vis[x + dx][y + dy]) continue; vis[x + dx][y + dy] = true; search.push_back({ x + dx, y + dy }); par[x + dx][y + dy] = { x, y }; } } return {}; } void solve_non_intersecting() { vector path = find_path(); if (path.empty()) { cout << "NO\n"; return; } vector sp = ordered(s, path[0].first, path[0].second); vector tp = ordered(t, path.back().first, path.back().second); reverse(all(sp)); vector> moves; queue cur; for (pll x : sp) { cur.push(x); } for (pll x : path | views::drop(1)) { pll y = cur.front(); cur.pop(); moves.push_back({ y, x }); cur.push(x); } for (pll x : tp | views::drop(1)) { pll y = cur.front(); cur.pop(); // cout << "final " << x.first << ' ' << x.second << ' ' << y.first << ' ' << y.second << '\n'; moves.push_back({ y, x }); } cout << "YES\n"; cout << ssize(moves) << '\n'; for (auto [ms, mt] : moves) { cout << (ms.first + 1) << ' ' << (ms.second + 1) << ' ' << (mt.first + 1) << ' ' << (mt.second + 1) << '\n'; } } void solve() { cin >> r >> c; o.resize(r, vector(c, false)); s.resize(r, vector(c, false)); t.resize(r, vector(c, false)); for (ll i = 0; i < r; ++i) { for (ll j = 0; j < c; ++j) { char c; cin >> c; if (c == '*') s[i][j] = true; if (c == 'X') o[i][j] = true; } } for (ll i = 0; i < r; ++i) { for (ll j = 0; j < c; ++j) { char c; cin >> c; if (c == '*') t[i][j] = true; if (c == 'X') o[i][j] = true; } } for (ll i = 0; i < r; ++i) { for (ll j = 0; j < c; ++j) { if (s[i][j] && t[i][j]) { solve_intersecting(i, j); return; } } } solve_non_intersecting(); } int main() { cin.tie(0)->sync_with_stdio(false); cout << setprecision(16); solve(); }