#include using namespace std; const int NMAX = 55; int N, M; bool blocked[NMAX][NMAX]; bool target[NMAX][NMAX], current[NMAX][NMAX]; bool need_to_move[NMAX][NMAX]; int viz[NMAX][NMAX]; int dist_to_target[NMAX][NMAX]; vector > Bfs(int x, int y, function CanGo) { vector > dist(N + 2, vector (M + 2, 1e9)); for (int i = 1; i <= N; i++) fill(viz[i], viz[i] + M + 1, 0); dist[x][y] = 0; viz[x][y] = 1; vector > q = { { x, y } }; for (int t = 0; t < (int)q.size(); t++) { auto [xx, yy] = q[t]; for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { if (dx != 0 && dy != 0) continue; int new_x = xx + dx, new_y = yy + dy; if (CanGo(new_x, new_y) && !blocked[new_x][new_y] && !viz[new_x][new_y]) { viz[new_x][new_y] = 1; dist[new_x][new_y] = 1 + dist[xx][yy]; q.push_back({ new_x, new_y }); } } } } return dist; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for (int i = 0; i <= N + 1; i++) for (int j = 0; j <= M + 1; j++) blocked[i][j] = 1; int nr1 = 0, nr2 = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { char c; cin >> c; blocked[i][j] = (c == 'X'); if (c == '*') nr1++, current[i][j] = 1; } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { char c; cin >> c; blocked[i][j] = (c == 'X'); if (c == '*') nr2++, target[i][j] = 1; } } if (nr1 != nr2) { cout << "NO\n"; return 0; } // find a cell of the final ameba not part of the first one int x_final = -1, y_final = -1; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) if (target[i][j] && !current[i][j]) x_final = i, y_final = j; if (x_final == -1) { cout << "YES\n0\n"; return 0; } auto dist_in_target = Bfs(x_final, y_final, [&](int x, int y) { return target[x][y] == 1; }); auto dist_global = Bfs(x_final, y_final, [&](int x, int y) { return blocked[x][y] == 0; }); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (current[i][j] && dist_global[i][j] > 1000) { cout << "NO\n"; return 0; } } } vector > answer; while (true) { // everything reachable from (x_final, y_final) is fixed auto dist_from_x_final = Bfs(x_final, y_final, [&](int x, int y) { return target[x][y] == 1 && current[x][y] == 1; }); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (dist_from_x_final[i][j] < 10000) need_to_move[i][j] = 0; else if (current[i][j]) need_to_move[i][j] = 1; } } // take the cell of the ameba closest to us int current_closest_x = -1, current_closest_y = -1, d = 1e9; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) { if (current[i][j] && need_to_move[i][j] && dist_global[i][j] < d) d = dist_global[i][j], current_closest_x = i, current_closest_y = j; } // finished if (d > 10000) { break; } // I now have a point in the ameba, (current_closest_x, current_closest_y) // I want to move the furthest away poitn of the ameba I need to one step closer auto dist_in_current = Bfs(current_closest_x, current_closest_y, [&](int x, int y) { return current[x][y] == 1 && need_to_move[x][y] == 0; }); int x_move = -1, y_move = -1; d = -1; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) if (dist_in_current[i][j] < 1000 && dist_in_current[i][j] > d) d = dist_in_current[i][j], x_move = i, y_move = j; // I will move (x_move, y_move) // 1st case: current_closest is touching final. Then, we expand anywhere we can if (abs(current_closest_x - x_final) + abs(current_closest_y - y_final) == 1) { int xx = -1, yy = -1; for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { if (dx != 0 && dy != 0) continue; int new_x = current_closest_x + dx, new_y = current_closest_y + dy; if (dist_global[new_x][new_y] + 1 == dist_global[current_closest_x][current_closest_y]) { // the one right before us xx = new_x; yy = new_y; } } } assert(xx != -1); answer.push_back(make_tuple(x_move, y_move, xx, yy)); current[x_move][y_move] = 0; assert(current[xx][yy] == 0); current[xx][yy] = 1; } else { // we can reach x_final. So expand to closest to it not reached yet. int xx = -1, yy = -1, d = 1e9; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) if (target[i][j] && dist_in_target[i][j] < d && !current[i][j]) d = dist_in_target[i][j], xx = i, yy = j; assert(xx != -1); answer.push_back(make_tuple(x_move, y_move, xx, yy)); current[x_move][y_move] = 0; assert(current[xx][yy] == 0); current[xx][yy] = 1; } } cout << "YES\n" << answer.size() << '\n'; for (auto [a, b, c, d] : answer) cout << a << ' ' << b << ' ' << c << ' ' << d << '\n'; }