#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, 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> dontmove(n, vector(m)); dontmove[ta][tb] = 1; while (true) { 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 (target[i][j] == '*' && a[i][j] != '*') { if (cx == -1 || dist[i][j] < dist[cx][cy]) { cx = i, cy = j; } } } } if (cx == -1) { break; } dist = vector(n, vector(m, -1)); dp = vector(n, vector(m)); dist[cx][cy] = 0; q.emplace(cx, cy); 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); } } } for (int i = 0; i < n; ++i) { bool ok = false; for (int j = 0; j < m; ++j) { if (a[i][j] == '*' && target[i][j] != '*' && is_connected_if_rem(a, i, j)) { fx = i, fy = j; ok = true; break; } if (a[i][j] == '*' && !dontmove[i][j] && is_connected_if_rem(a, i, j)) { fx = i, fy = j; } } if (ok) break; } if (fy == -1) { break; } sol.emplace_back(make_pair(fx, fy), make_pair(cx, cy)); swap(a[fx][fy], a[cx][cy]); dontmove[cx][cy] = 1; } if (a == target) { 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; } cout << "NO\n"; return 0; }