#include //#pragma GCC optimize("O3") //#define int long long using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair pii; typedef vector vi; vector> vis, visited; vector> path; int r, c; vector starting, ending; pair dfs2(int i, int j) { vis[i][j] = true; for (int di = -1; di <= +1; ++di) for (int dj = -1; dj <= +1; ++dj) if (abs(di) + abs(dj) == 1) { int ni = i + di; int nj = j + dj; if (ni >= 0 && ni < r && nj >= 0 && nj < c) { if (!vis[ni][nj] && starting[ni][nj] == '*') { return dfs2(ni, nj); } } } return {i, j}; }; bool dfs(int i, int j) { path.push_back({i, j}); if (starting[i][j] == '*') return true; visited[i][j] = true; for (int di = -1; di <= +1; ++di) for (int dj = -1; dj <= +1; ++dj) if (abs(di) + abs(dj) == 1) { int ni = i + di; int nj = j + dj; if (ni >= 0 && ni < r && nj >= 0 && nj < c) { if (!visited[ni][nj] && starting[ni][nj] != 'X') { if(dfs(ni, nj)) return true; } } } path.pop_back(); return false; }; signed main(){ cin.tie(0); ios::sync_with_stdio(0); string emp; getline(cin, emp); stringstream ss(emp); ss >> r >> c; starting = vector(r); ending = vector(r); vector> moves; for (string& s : starting) getline(cin, s); getline(cin, emp); for (string& s : ending) getline(cin, s); auto equal = [&] () { for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) if (starting[i][j] == '*' && ending[i][j] != '*') return false; return true; }; auto prnt = [&] () { for (int i = 0; i < r; ++i, cout << '\n') for (int j = 0; j < c; ++j) cerr << starting[i][j]; cerr << endl; }; bool overlap = false; for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) if (starting[i][j] == '*' && ending[i][j] == '*') overlap = true; if (!overlap) { pair s; for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) if (ending[i][j] == '*') s = {i, j}; visited = vector>(r, vector(c)); if (!dfs(s.first, s.second)) { cout << "NO\n"; return 0; } } auto add_move = [&] (int a, int b, int c, int d) { // cerr << a << ' ' << b << ' ' << c << ' ' << d << endl; starting[a][b] = '.'; starting[c][d] = '*'; moves.push_back(vector{a, b, c, d}); }; while (path.size() > 1) { // cerr << path.back().first << ' ' << path.back().second << endl; vis = vector>(r, vector(c)); pair lst = dfs2(path.back().first, path.back().second); // cerr << lst.first << ' ' << lst.second << endl; path.pop_back(); // cerr << path.back().first << ' ' << path.back().second << endl; // prnt(); add_move(lst.first, lst.second, path.back().first, path.back().second); // prnt(); // check connected perhaps? } while (!equal()) { vector> dists(r, vector(c, -1)); queue> q; for (int i = 0; i < r; ++i) for (int j = 0; j < c; ++j) if (starting[i][j] == '*' && ending[i][j] == '*') { dists[i][j] = 0; q.push({i, j}); } pair rmv, add; bool set_add = false, set_rmv = false; while (q.size()) { auto [x, y] = q.front(); q.pop(); rmv = {x, y}; set_rmv = true; for (int di = -1; di <= +1; ++di) for (int dj = -1; dj <= +1; ++dj) if (abs(di) + abs(dj) == 1) { int ni = x + di; int nj = y + dj; if (ni >= 0 && ni < r && nj >= 0 && nj < c) { if (dists[ni][nj] == -1 && starting[ni][nj] == '*') { dists[ni][nj] = dists[x][y] + 1; q.push({ni, nj}); } if (starting[ni][nj] == '.' && ending[ni][nj] == '*' && dists[x][y] == 0) { add = {ni, nj}; set_add = true; } } } } assert(set_add); assert(set_rmv); assert(add != rmv); add_move(rmv.first, rmv.second, add.first, add.second); } cout << "YES\n"; cout << moves.size() << '\n'; for (auto& vec : moves) { for (int v : vec) cout << v + 1 << ' '; cout << '\n'; } return 0; }