#pragma GCC optimize ("O3") #include "bits/stdc++.h" using namespace std; #define rep(i, b, e) for(int i = (b); i <= (e); i++) #define per(i, b, e) for(int i = (e); i >= (b); i--) #define FOR(i, b, e) rep(i, b, (e) - 1) #define SZ(x) int(x.size()) #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define st first #define nd second using ll = long long; using pii = pair; using vi = vector; auto &operator<<(auto &o, pair p) { return o << "(" << p.st << ", " << p.nd << ")"; } auto operator<<(auto &o, auto x)->decltype(end(x), o) { o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e; return o << "}"; } #ifdef LOCAL #define deb(x...) cerr << "[" #x << "]: ", [](auto...$) { ((cerr << $ << "; "),...) << endl; }(x) #else #define deb(...) #endif using mapa = vector; int n, m; const int INF = 1e9 + 7; bool ok(int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; } int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; vector bfs(pii start, mapa &ma) { vector dst(n, vi(m, INF)); queue q; dst[start.st][start.nd] = 0; q.push(start); while(!q.empty()) { auto [x, y] = q.front(); q.pop(); FOR(k, 0, 4) { int nx = x + dx[k], ny = y + dy[k]; if(!ok(nx, ny) || ma[nx][ny] == 'X' || dst[nx][ny] != INF) continue; dst[nx][ny] = dst[x][y] + 1; q.push({nx, ny}); } } return dst; } void solve() { cin >> n >> m; mapa a(n), b(n); FOR(i, 0, n) cin >> a[i]; FOR(i, 0, n) cin >> b[i]; pair> best = {INF, {{-1, -1}, {-1, -1}}}; FOR(i, 0, n) FOR(j, 0, m) if(a[i][j] == '*') { auto res = bfs({i, j}, a); FOR(k, 0, n) FOR(l, 0, m) if(b[k][l] == '*') { best = min(best, {res[k][l], {{i, j}, {k, l}}}); } } if(best.st == INF) { cout << "NO\n"; return; } pii start = best.nd.st; auto dst = bfs(start, a); vector path; for(pii akt = best.nd.nd; dst[akt.st][akt.nd] > 0; ) { path.pb(akt); FOR(k, 0, 4) { int nx = akt.st + dx[k], ny = akt.nd + dy[k]; if(ok(nx, ny) && dst[nx][ny] + 1 == dst[akt.st][akt.nd]) { akt = {nx, ny}; break; } } } reverse(all(path)); vector> moves; deque goms; FOR(i, 0, n) FOR(j, 0, m) if(a[i][j] == '*') goms.pb({i, j}); sort(all(goms), [&dst](const pii &aa, const pii &bb) { return dst[aa.st][aa.nd] > dst[bb.st][bb.nd]; }); for(auto &[x, y]: path) { pii kto = goms.front(); goms.pop_front(); a[kto.st][kto.nd] = '.'; moves.pb({kto, {x, y}}); a[x][y] = '*'; goms.pb({x, y}); } pii meet = best.nd.nd; dst = bfs(meet, a); vector lewi, prawi; FOR(i, 0, n) FOR(j, 0, m) { if(a[i][j] == '*' && b[i][j] != '*') lewi.pb({i, j}); if(a[i][j] != '*' && b[i][j] == '*') prawi.pb({i, j}); } sort(all(lewi), [&dst](const pii &aa, const pii &bb) { return dst[aa.st][aa.nd] > dst[bb.st][bb.nd]; }); sort(all(prawi), [&dst](const pii &aa, const pii &bb) { return dst[aa.st][aa.nd] < dst[bb.st][bb.nd]; }); FOR(i, 0, SZ(lewi)) moves.pb({lewi[i], prawi[i]}); cout << "YES\n" << SZ(moves) << "\n"; for(auto &[x, y]: moves) { cout << x.st + 1 << ' ' << x.nd + 1 << ' ' << y.st + 1 << ' ' << y.nd + 1 << '\n'; } } int main() { cin.tie(0)->sync_with_stdio(0); int tt = 1; // cin >> tt; FOR(te, 0, tt) solve(); return 0; }