#include using namespace std; #pragma GCC target("avx2") #pragma GCC optimize("O3") int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int n, m; int all = 0; bool is_connected_if_rem(vector &a, int x, int y) { int cnt = 0; for (int i = 0; i < a.size(); ++i) { for (int j = 0; j < a[1].size(); ++j) { if(a[i][j] == '*' && (i != x || j != y)) { queue> q; vector> vis(a.size(), vector(a[0].size())); vis[i][j] = 1; q.emplace(i, j); while(q.size()) { int xx, yy; tie(xx, yy) = q.front(); q.pop(); for (int dir = 0; dir < 4; ++dir) { int nx = xx + dx[dir]; int ny = yy + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] != '*' || (nx == x && ny == y)) continue; if (vis[nx][ny] == 0) { vis[nx][ny] = 1; ++cnt; q.emplace(nx, ny); } } } return cnt == all - 2; } } } assert(false); return 0; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; vector a(n); vector target(n); for (auto &x : a) cin >> x; for (auto &x : target) cin >> x; int ta = 0, tb = 0; // Step 1 : get amanda to some cell in the solution for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (target[i][j] == '*') { all += 1; ta = i; tb = j; } } } { vector> dist(n, vector(m, -1)); dist[ta][tb] = 0; queue> q; q.emplace(ta, tb); while(q.size()) { int x, y; tie(x, y) = q.front(); q.pop(); for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == 'X') continue; if (dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } } for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if ((a[i][j] == '*' || target[i][j] == '*') && dist[i][j] == -1) { cout << "NO\n"; return 0; } } } } vector, pair>> sol; while (a[ta][tb] != '*') { vector> dist(n, vector(m, -1)); vector> dp(n, vector(m)); dist[ta][tb] = 0; queue> q; q.emplace(ta, tb); while(q.size()) { int x, y; tie(x, y) = q.front(); q.pop(); for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] == 'X') continue; if (dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; dp[nx][ny] = dir; q.emplace(nx, ny); } } } // find the closest and farthest; int cx = -1, cy = -1, fx = -1, fy = -1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == '*') { if (cx == -1 || dist[i][j] < dist[cx][cy]) { cx = i, cy = j; } if (fx == -1 || dist[i][j] > dist[fx][fy]) { fx = i, fy = j; } } } } sol.emplace_back(make_pair(fx, fy), make_pair(cx - dx[dp[cx][cy]], cy - dy[dp[cx][cy]])); swap(a[fx][fy], a[cx - dx[dp[cx][cy]]][cy - dy[dp[cx][cy]]]); } vector> orderamiba; vector> ordersol; { vector> dist(n, vector(m, -1)); dist[ta][tb] = 0; queue> q; q.emplace(ta, tb); while(q.size()) { int x, y; tie(x, y) = q.front(); q.pop(); orderamiba.emplace_back(x, y); for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx][ny] != '*') continue; if (dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } } dist = vector(n, vector(m, -1)); dist[ta][tb] = 0; q.emplace(ta, tb); while(q.size()) { int x, y; tie(x, y) = q.front(); q.pop(); ordersol.emplace_back(x, y); for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || target[nx][ny] != '*') continue; if (dist[nx][ny] == -1) { dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } } } vector> solved(n + 1, vector (m + 1)); reverse(orderamiba.begin(), orderamiba.end()); int ptr = 0; for (auto &x: ordersol) { while (ptr < orderamiba.size() && solved[orderamiba[ptr].first][orderamiba[ptr].second]) ++ptr; if (ptr == orderamiba.size()) break; if (a[x.first][x.second] == '*') { solved[x.first][x.second] = 1; } else { swap(a[orderamiba[ptr].first][orderamiba[ptr].second], a[x.first][x.second]); sol.emplace_back(orderamiba[ptr], x); ++ptr; } } cout << "YES\n"; cout << sol.size() << '\n'; for (auto &x : sol) { cout << x.first.first + 1 << ' ' << x.first.second + 1 << ' ' << x.second.first + 1 << ' ' << x.second.second + 1 << '\n'; } return 0; }