#include using namespace std; #define rep(i,a,b) for (int i = a; i < b; i++) #define trav(a,b) for (auto a : b) #define all(x) begin(x),end(x) #define lld long long void Solve() { int r, c; cin >> r >> c; vector< vector > m1(r, vector(c)); vector< vector > m2(r, vector(c)); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> m1[i][j]; } } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { cin >> m2[i][j]; } } pair source; vector< pair > path; { queue< pair > q; const int INF = 1e9; vector< vector > dist(r, vector(c, INF)); vector< vector< pair > > f(r, vector< pair >(c, {-1, -1})); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (m1[i][j] == '*') { q.emplace(i, j); dist[i][j] = 0; } } } vector dr = {+1, -1, +0, +0}; vector dc = {+0, +0, -1, +1}; while (!q.empty()) { auto [ri, ci] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { if (ri + dr[i] < 0) continue; if (ri + dr[i] >= r) continue; if (ci + dc[i] < 0) continue; if (ci + dc[i] >= c) continue; if (m1[ri + dr[i]][ci + dc[i]] == 'X') continue; if (dist[ri + dr[i]][ci + dc[i]] > dist[ri][ci] + 1) { q.emplace(ri + dr[i], ci + dc[i]); dist[ri + dr[i]][ci + dc[i]] = dist[ri][ci] + 1; f[ri + dr[i]][ci + dc[i]] = {ri, ci}; } } } int d = INF; pair pos; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (m2[i][j] == '*' && d > dist[i][j]) { d = min(d, dist[i][j]); pos = {i, j}; } } } if (d == INF) { cout << "NO" << '\n'; return; } cout << "YES" << '\n'; while (dist[ pos.first ][ pos.second ] != 0) { path.emplace_back(pos); pos = f[pos.first][pos.second]; } // for (auto [ri, ci] : path) cout << ri << ' ' << ci << '\n'; reverse(path.begin(), path.end()); source = pos; if(path.size() != 0) { source = path.back(); } } auto longest_cell = [&](int r_source, int c_source) { queue< pair > q; q.emplace(r_source, c_source); const int INF = 1e9; vector< vector > dist(r, vector(c, INF)); dist[r_source][c_source] = 0; vector< vector< pair > > f(r, vector< pair >(c, {-1, -1})); vector dr = {+1, -1, +0, +0}; vector dc = {+0, +0, -1, +1}; while (!q.empty()) { auto [ri, ci] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { if (ri + dr[i] < 0) continue; if (ri + dr[i] >= r) continue; if (ci + dc[i] < 0) continue; if (ci + dc[i] >= c) continue; if (m1[ri + dr[i]][ci + dc[i]] == 'X') continue; if (dist[ri + dr[i]][ci + dc[i]] > dist[ri][ci] + 1) { q.emplace(ri + dr[i], ci + dc[i]); dist[ri + dr[i]][ci + dc[i]] = dist[ri][ci] + 1; f[ri + dr[i]][ci + dc[i]] = {ri, ci}; } } } int d = -1; pair pos; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (m1[i][j] == '*' && dist[i][j] > d) { d = dist[i][j]; pos = {i, j}; } } } return pos; }; vector< array > ANS; auto move_to = [&](int r_start, int c_start, int r_end, int c_end) { assert(m1[r_start][c_start] == '*'); assert(m1[r_end][c_end] == '.'); ANS.push_back({r_start + 1, c_start + 1, r_end + 1, c_end + 1}); // cout << r_start + 1 << ' ' << c_start + 1 << ' ' << r_end + 1 << ' ' << c_end + 1 << '\n'; swap(m1[r_start][c_start], m1[r_end][c_end]); }; for (auto & [pr, pc] : path) { auto [r_longest, c_longest] = longest_cell(pr, pc); move_to(r_longest, c_longest, pr, pc); } while (true){ queue< pair > q; q.emplace(source.first, source.second); const int INF = 1e9; vector< vector > dist(r, vector(c, INF)); dist[source.first][source.second] = 0; // vector< vector< pair > > f(r, vector< pair >(c, {-1, -1})); vector dr = {+1, -1, +0, +0}; vector dc = {+0, +0, -1, +1}; // vector< pair > // path.clear(); pair expandTo = {-1, -1}; // cout << "S:" << '\n'; while (!q.empty()) { auto [ri, ci] = q.front(); q.pop(); // cout << ri << ' ' << ci << '\n'; // path.emplace_back(ri, ci); if (m1[ri][ci] == '*') { for (int i = 0; i < 4; i++) { if (ri + dr[i] < 0) continue; if (ri + dr[i] >= r) continue; if (ci + dc[i] < 0) continue; if (ci + dc[i] >= c) continue; if (m2[ri + dr[i]][ci + dc[i]] != '*') continue; // if (m1[ri + dr[i]][ci + dc[i]] == '*') continue; if (dist[ri + dr[i]][ci + dc[i]] > dist[ri][ci] + 1) { q.emplace(ri + dr[i], ci + dc[i]); dist[ri + dr[i]][ci + dc[i]] = dist[ri][ci] + 1; } } } else { expandTo = {ri, ci}; } } if (expandTo == make_pair(-1, -1)) { break; } { // copied from longest queue< pair > q; q.emplace(expandTo.first, expandTo.second); const int INF = 1e9; vector< vector > dist2(r, vector(c, INF)); for (int i = 0; i < 4; i++) { int ri = expandTo.first; int ci = expandTo.second; if (ri + dr[i] < 0) continue; if (ri + dr[i] >= r) continue; if (ci + dc[i] < 0) continue; if (ci + dc[i] >= c) continue; if (dist[ri + dr[i]][ci + dc[i]] != INF) { q.emplace(ri + dr[i], ci + dc[i]); dist2[ri + dr[i]][ci + dc[i]] = 1; } } // dist2[expandTo.first][expandTo.second] = 0; vector< vector< pair > > f(r, vector< pair >(c, {-1, -1})); vector dr = {+1, -1, +0, +0}; vector dc = {+0, +0, -1, +1}; while (!q.empty()) { auto [ri, ci] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { if (ri + dr[i] < 0) continue; if (ri + dr[i] >= r) continue; if (ci + dc[i] < 0) continue; if (ci + dc[i] >= c) continue; if (m1[ri + dr[i]][ci + dc[i]] != '*') continue; if (dist2[ri + dr[i]][ci + dc[i]] > dist2[ri][ci] + 1) { q.emplace(ri + dr[i], ci + dc[i]); dist2[ri + dr[i]][ci + dc[i]] = dist2[ri][ci] + 1; f[ri + dr[i]][ci + dc[i]] = {ri, ci}; } } } int d = -1; pair pos; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (m1[i][j] == '*' && dist2[i][j] > d && dist[i][j] == INF) { // except this d = dist2[i][j]; pos = {i, j}; } } } move_to(pos.first, pos.second, expandTo.first, expandTo.second); } } cout << (int) ANS.size() << '\n'; for (auto [a, b, c, d] : ANS) cout << a << ' ' << b << ' ' << c << ' ' << d << '\n'; // cout << (int // pair s; // if (path.size() != 0) { // s = path.back(); // } // for (int i = 0; i < r; i++) { // for (int j = 0; j < c; j++) { // if (m2[i][j] == '*' && m1[i][j] == '*') { // return; // } // } // } } signed main() { ios::sync_with_stdio(0); cin.tie(0); int tt = 1; // cin >> tt; while (tt--) Solve(); return 0; }