#include using namespace std; #define Dv(v) for (auto x : v) cerr << x << ' '; cerr << endl; #define D(x) cerr << #x << " = " << x << ", " using ll = long long; using vi = vector; using vvi = vector; int r, c; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> r >> c; vector starting(r+2), target(r+2); starting[0] = starting[r+1] = string(c+2,'X'); target[0] = target[r+1] = string(c+2,'X'); for (int i = 1; i <= r; ++i) { cin >> starting[i]; starting[i] = "X" + starting[i] + "X"; } for (int i = 1; i <= r; ++i) { cin >> target[i]; target[i] = "X" + target[i] + "X"; } vector> dists(r+2, vector(c+2)); for (int i = 0; i <= r+1; ++i) { for (int j = 0; j <= c+1; ++j) { dists[i][j] = 1e9; } } priority_queue>> PQ; for (int i = 1; i <= r; ++i) { for (int j = 1; j <= c; ++j) { if (target[i][j] == '*') { dists[i][j] = 0; PQ.push({0, {i, j}}); } } } while (!PQ.empty()) { auto [d, p] = PQ.top(); d = -d; PQ.pop(); if (d > dists[p.first][p.second]) continue; if (starting[p.first+1][p.second] != 'X' && dists[p.first+1][p.second] > d+1) { dists[p.first+1][p.second] = d+1; PQ.push({-d-1, {p.first+1, p.second}}); } if (starting[p.first-1][p.second] != 'X' && dists[p.first-1][p.second] > d+1) { dists[p.first-1][p.second] = d+1; PQ.push({-d-1, {p.first-1, p.second}}); } if (starting[p.first][p.second+1] != 'X' && dists[p.first][p.second+1] > d+1) { dists[p.first][p.second+1] = d+1; PQ.push({-d-1, {p.first, p.second+1}}); } if (starting[p.first][p.second-1] != 'X' && dists[p.first][p.second-1] > d+1) { dists[p.first][p.second-1] = d+1; PQ.push({-d-1, {p.first, p.second-1}}); } } //check if possible & collect set>> myCells; for (int i = 1; i <= r; ++i) { for (int j = 1; j <= c; ++j) { if (starting[i][j] == '*') { if (dists[i][j] > 1e8) { cout << "NO\n"; return 0; } myCells.insert({dists[i][j], {i, j}}); } } } // cerr << "cells:" << endl; // for (auto [d, p] : myCells) { // cerr << d << ":" << p.first << ',' << p.second << endl; // } // cerr << endl; vector, pair>> ans; pair last = {-1, -1}; while (myCells.rbegin()->first > 0) { pair origin = myCells.begin()->second; if (last != pair{-1, -1}) origin = last; int d = dists[origin.first][origin.second]; if (d > 0) --d; // cerr << "origin " << origin.first << ' ' << origin.second << endl; pair goTo = {-1, -1}; if (starting[origin.first+1][origin.second] == '.' && dists[origin.first+1][origin.second] == d) { goTo = {origin.first+1, origin.second}; } else if (starting[origin.first-1][origin.second] == '.' && dists[origin.first-1][origin.second] == d) { goTo = {origin.first-1, origin.second}; } else if (starting[origin.first][origin.second+1] == '.' && dists[origin.first][origin.second+1] == d) { goTo = {origin.first, origin.second+1}; } else if (starting[origin.first][origin.second-1] == '.' && dists[origin.first][origin.second-1] == d) { goTo = {origin.first, origin.second-1}; } else { myCells.erase(myCells.begin()); if (myCells.empty()) { for (int i = 1; i <= r; ++i) { for (int j = i; j <= c; ++j) { if (starting[i][j] == '*') { myCells.insert({dists[i][j], {i, j}}); } } } } last = {-1, -1}; continue; } // for (int i = 0; i <= r+1; ++i) { // for (int j = 0; j <= c+1; ++j) { // cerr << starting[i][j]; // } // cerr << endl; // } // cerr << endl; assert((goTo != pair{-1, -1})); vector> inDist(r+2, vector(c+2, 1e9)); queue> S; S.push(origin); inDist[origin.first][origin.second] = 0; pair far = origin; pair farBad = {-1, -1}; int cnt1 = 0; while (!S.empty()) { pair act = S.front(); S.pop(); cnt1++; if (dists[act.first][act.second] > 0) farBad = act; far = act; if (starting[act.first+1][act.second] == '*' && inDist[act.first+1][act.second] > 1e8) { inDist[act.first+1][act.second] = inDist[act.first][act.second]+1; S.push({act.first+1, act.second}); } if (starting[act.first-1][act.second] == '*' && inDist[act.first-1][act.second] > 1e8) { inDist[act.first-1][act.second] = inDist[act.first][act.second]+1; S.push({act.first-1, act.second}); } if (starting[act.first][act.second+1] == '*' && inDist[act.first][act.second+1] > 1e8) { inDist[act.first][act.second+1] = inDist[act.first][act.second]+1; S.push({act.first, act.second+1}); } if (starting[act.first][act.second-1] == '*' && inDist[act.first][act.second-1] > 1e8) { inDist[act.first][act.second-1] = inDist[act.first][act.second]+1; S.push({act.first, act.second-1}); } } // for (int i = 0; i <= r+1; ++i) { // for (int j = 0; j <= c+1; ++j) { // if (starting[i][j] == '*') // cerr << inDist[i][j] << ' '; // else cerr << starting[i][j] << ' '; // } // cerr << endl; // } // cerr << endl; // try removing farbad // cerr << "far: " << far.first << ' ' << far.second << endl; // cerr << "farBad: " << farBad.first << ' ' << farBad.second << endl; pair remove = farBad; starting[farBad.first][farBad.second] = '.'; inDist = vector>(r+2, vector(c+2, 1e9)); if (remove != origin) S.push(origin); inDist[origin.first][origin.second] = 0; int cnt2 = 0; while (!S.empty()) { pair act = S.front(); S.pop(); cnt2++; if (starting[act.first+1][act.second] == '*' && inDist[act.first+1][act.second] > 1e8) { inDist[act.first+1][act.second] = inDist[act.first][act.second]+1; S.push({act.first+1, act.second}); } if (starting[act.first-1][act.second] == '*' && inDist[act.first-1][act.second] > 1e8) { inDist[act.first-1][act.second] = inDist[act.first][act.second]+1; S.push({act.first-1, act.second}); } if (starting[act.first][act.second+1] == '*' && inDist[act.first][act.second+1] > 1e8) { inDist[act.first][act.second+1] = inDist[act.first][act.second]+1; S.push({act.first, act.second+1}); } if (starting[act.first][act.second-1] == '*' && inDist[act.first][act.second-1] > 1e8) { inDist[act.first][act.second-1] = inDist[act.first][act.second]+1; S.push({act.first, act.second-1}); } } starting[farBad.first][farBad.second] = '*'; if (cnt2+1 < cnt1) { remove = far; } // cerr << "remove " << remove.first << ' ' << remove.second << endl; ans.push_back({remove, goTo}); starting[remove.first][remove.second] = '.'; starting[goTo.first][goTo.second] = '*'; myCells.erase({dists[remove.first][remove.second], remove}); myCells.insert({d, goTo}); last = goTo; } cout << "YES\n"; cout << ans.size() << '\n'; for (auto [p, q] : ans) { cout << p.first << ' ' << p.second << ' ' << q.first << ' ' << q.second << '\n'; } }