#include using namespace std; using vi = vector; using vvi = vector; using ll = long long; using vll = vector; using vvll = vector; using pii = pair; using vpii = vector; void solve() { int n, m; cin >> n >> m; vector start(n); vector finish(n); for(int i = 0; i < n; i++) { cin >> start[i]; } for(int i = 0; i < n; i++) { cin >> finish[i]; } // cerr << "input done" << endl; // for(int i = 0; i < n; i++) { // cerr << start[i] << endl; // } // for(int i = 0; i < n; i++) { // cerr << finish[i] << endl; // } vector mask = start; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(mask[i][j] == '*') { mask[i][j] = '.'; } } } pii rt; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(start[i][j] == '*') { rt = {i, j}; } } } vector par(n, vpii(m)); vvi dep(n, vi(m, -1)); queue q; q.push(rt); par[rt.first][rt.second] = {-1, -1}; dep[rt.first][rt.second] = 0; while(!q.empty()) { pii from = q.front(); q.pop(); for(int dx = -1; dx <= 1; dx++) { for(int dy = -1; dy <= 1; dy++) { if(abs(dx) + abs(dy) == 1) { pii to = {from.first - dx, from.second + dy}; if(0 <= to.first && to.first < n && 0 <= to.second && to.second < m && dep[to.first][to.second] == -1 && mask[to.first][to.second] == '.') { dep[to.first][to.second] = dep[from.first][from.second] + 1; par[to.first][to.second] = from; q.push(to); } } } } } // cerr << "foo" << endl; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(finish[i][j] == '*' && dep[i][j] == -1) { cout << "NO" << endl; return; } } } int size = 0; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(start[i][j] == '*') { size++; } } } vector> depths; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(dep[i][j] >= 0) { depths.push_back({dep[i][j], {i, j}}); } } } sort(depths.begin(), depths.end()); vector nf = mask; for(int i = 0; i < size; i++) { pii p = depths[i].second; mask[p.first][p.second] = '*'; } // cerr << "preprocess done" << endl; auto to_nf = [&](vector start) { vector cur = start; vector> ans; int min_dep = 1e9; pii min_dep_cur = {-1, -1}; deque order; int max_dep = -1; pii max_dep_cur = {-1, -1}; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(dep[i][j] != -1 && cur[i][j] == '*' && dep[i][j] < min_dep) { min_dep = dep[i][j]; min_dep_cur = {i, j}; } if(dep[i][j] != -1 && cur[i][j] == '*' && dep[i][j] > max_dep) { max_dep = dep[i][j]; max_dep_cur = {i, j}; } } } queue r; vvi vis(n, vi(m)); vis[min_dep_cur.first][min_dep_cur.second] = true; order.push_back(min_dep_cur); r.push(min_dep_cur); while(!r.empty()) { pii from = r.front(); r.pop(); for(int dx = -1; dx <= 1; dx++) { for(int dy = -1; dy <= 1; dy++) { if(abs(dx) + abs(dy) == 1) { pii to = {from.first - dx, from.second + dy}; if(0 <= to.first && to.first < n && 0 <= to.second && to.second < m && start[to.first][to.second] == '*' && !vis[to.first][to.second]) { vis[to.first][to.second] = true; r.push(to); order.push_back(to); } } } } } auto move = [&](pii from, pii to) { ans.push_back({from, to}); assert(cur[from.first][from.second] == '*'); cur[from.first][from.second] = '.'; assert(cur[to.first][to.second] == '.'); cur[to.first][to.second] = '*'; }; // cerr << "start phase 1" << endl; pii cur_ptr = min_dep_cur; while(cur_ptr != rt) { // cerr << cur_ptr.first << ' ' << cur_ptr.second << endl; cur_ptr = par[cur_ptr.first][cur_ptr.second]; // cerr << cur_ptr.first << ' ' << cur_ptr.second << endl; pii from = order.back(); order.pop_back(); move(from, cur_ptr); order.push_front(cur_ptr); } // cerr << "phase 1 done" << endl; vector> good(n, vector(m)); for(int i = 0; i < size; i++) { pii cand = depths[i].second; if(cur[cand.first][cand.second] == '*') { continue; } pii from = {-1, -1}; while(from.first == -1) { pii p = order.back(); order.pop_back(); if(good[p.first][p.second]) continue; from = p; } move(from, cand); } // for(int i = 0; i < size; i++) { // pii cand = depths[i].second; // pii p = order.back(); // if(cur[cand.first][cand.second] == '.') { // move(p, cand); // } // // if(cur[cand.first][cand.second] == '.') { // // pii from = {-1, -1}; // // while(from.first == -1) { // // pii p = order.back(); // // order.pop_back(); // // if(nf[p.first][p.second] == '.') { // // from = p; // // break; // // } // // } // // move(from, cand); // // } // } return ans; }; auto ans1 = to_nf(start); auto ans2 = to_nf(finish); cout << "YES" << endl; cout << ans1.size() + ans2.size() << endl; reverse(ans2.begin(), ans2.end()); for(auto p : ans1) { cout << p.first.first + 1 << ' ' << p.first.second + 1 << ' ' << p.second.first + 1 << ' ' << p.second.second + 1 << endl; } // cerr << "--------------" << endl; for(auto p : ans2) { cout << p.second.first + 1 << ' ' << p.second.second + 1 << ' ' << p.first.first + 1 << ' ' << p.first.second + 1 << endl; } } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int tc = 1; while(tc--) { solve(); } }