#include #define X first #define Y second using namespace std; int n, m; char c[55][55]; char d[55][55]; int px, py, kx, ky; queue< pair > q; int bio[55][55]; pair dosao[55][55]; int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; vector< pair > put; vector< pair< pair, pair > > sol; void bfs() { while (!q.empty()) { int x = q.front().X; int y = q.front().Y; q.pop(); for (int i = 0; i < 4; i++) { int x2 = x + dx[i]; int y2 = y + dy[i]; if (x2 >= 0 && y2 >= 0 && x2 < n && y2 < m && c[x2][y2] != 'X' && bio[x2][y2] == -1) { bio[x2][y2] = bio[x][y] + 1; dosao[x2][y2] = {x, y}; q.push({x2, y2}); } } } } void recput(int x, int y) { if (c[x][y] == '*') { px = x; py = y; return; } recput(dosao[x][y].X, dosao[x][y].Y); put.push_back({x, y}); } void rek(int x, int y) { bio[x][y] = 1; for (int i = 0; i < 4; i++) { int x2 = x + dx[i]; int y2 = y + dy[i]; if (x2 >= 0 && y2 >= 0 && x2 < n && y2 < m && c[x2][y2] == '*' && bio[x2][y2] == 0) { rek(x2, y2); } } q.push({x, y}); } vector< pair > poredak; void dfs(int x, int y) { bio[x][y] = 1; poredak.push_back({x, y}); for (int i = 0; i < 4; i++) { int x2 = x + dx[i]; int y2 = y + dy[i]; if (x2 >= 0 && y2 >= 0 && x2 < n && y2 < m && d[x2][y2] == '*' && bio[x2][y2] == 0) { dfs(x2, y2); } } } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { bio[i][j] = -1; cin >> c[i][j]; if (c[i][j] == '*') px = i, py = j; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> d[i][j]; if (d[i][j] == '*') kx = i, ky = j; } } q.push({px, py}); bio[px][py] = 0; bfs(); if (bio[kx][ky] == -1) { cout << "NO"; return 0; } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { bio[i][j] = 0; } } recput(kx, ky); bio[px][py] = 1; rek(px, py); cout << "YES\n"; for (int i = 0; i < put.size(); i++) { sol.push_back({{q.front().X, q.front().Y}, {put[i].X, put[i].Y}}); c[q.front().X][q.front().Y] = '.'; c[put[i].X][put[i].Y] = '*'; q.push(put[i]); q.pop(); } //cout << px << " " << py << " " << kx << " " << ky << endl; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { bio[i][j] = 0; } } dfs(kx, ky); int rep = 2500; while (rep--) { for (int i = 0; i < poredak.size(); i++) { if (c[poredak[i].X][poredak[i].Y] != '*') { c[q.front().X][q.front().Y] = '.'; sol.push_back({{q.front().X, q.front().Y}, {poredak[i].X, poredak[i].Y}}); c[poredak[i].X][poredak[i].Y] = '*'; q.push(poredak[i]); q.pop(); } } } cout << sol.size() << "\n"; for (int i = 0; i < sol.size(); i++) { cout << sol[i].X.X+1 << " " << sol[i].X.Y+1 << " " << sol[i].Y.X+1 << " " << sol[i].Y.Y+1 << "\n"; } return 0; }