#include using namespace std; struct Move { int a, b, c, d; }; const int N_MAX = 50; int N, M; char A[N_MAX + 5][N_MAX + 5]; char B[N_MAX + 5][N_MAX + 5]; pair prv[N_MAX + 5][N_MAX + 5]; bool vis[N_MAX + 5][N_MAX + 5]; int di[] = {1, -1, 0, 0}; int dj[] = {0, 0, 1, -1}; vector < pair > make_path() { queue < pair > Q; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { if(A[i][j] == '*') { Q.push(make_pair(i, j)); prv[i][j] = make_pair(i, j); } } } vector > ret; auto ok_pos = [&](int i, int j) { return i >= 1 && i <= N && j >= 1 && j <= M && prv[i][j] == make_pair(0, 0) && A[i][j] != 'X'; }; while(!Q.empty()) { auto [i, j] = Q.front(); Q.pop(); if(B[i][j] == '*') { int x = i, y = j; while(prv[x][y] != make_pair(x, y)) { ret.push_back(make_pair(x, y)); tie(x, y) = prv[x][y]; } ret.push_back(make_pair(x, y)); reverse(ret.begin(), ret.end()); return ret; } for(int d = 0; d < 4; d++) { int ii = i + di[d]; int jj = j + dj[d]; if(ok_pos(ii, jj)) { prv[ii][jj] = make_pair(i, j); Q.push(make_pair(ii, jj)); } } } return ret; } vector < pair > get_ordered_by_layer(int x, int y, char A[][N_MAX + 5]) { vector > ret; queue < pair > Q; memset(vis, false, sizeof(vis)); vis[x][y] = true; Q.push(make_pair(x, y)); auto ok_pos = [&](int i, int j) { return i >= 1 && i <= N && j >= 1 && j <= M && !vis[i][j] && A[i][j] == '*'; }; while(!Q.empty()) { auto [i, j] = Q.front(); Q.pop(); ret.push_back(make_pair(i, j)); for(int d = 0; d < 4; d++) { int ii = i + di[d]; int jj = j + dj[d]; if(ok_pos(ii, jj)) { vis[ii][jj] = true; Q.push(make_pair(ii, jj)); } } } return ret; } vector move_amoeba(vector > path) { auto [s_x, s_y] = path[0]; auto [f_x, f_y] = path.back(); auto layer_del = get_ordered_by_layer(s_x, s_y, A); auto layer_add = get_ordered_by_layer(f_x, f_y, B); reverse(layer_del.begin(), layer_del.end()); if(path.size() > 2) { layer_del.insert(layer_del.end(), path.begin() + 1, path.end() - 1); layer_add.insert(layer_add.begin(), path.begin() + 1, path.end() - 1); } memset(vis, false, sizeof(vis)); vector ret; // cerr << path.size() << "\n\n"; // for(auto it : layer_del) { // cerr << it.first << " " << it.second << "\n"; // } // cerr << "\n"; // for(auto it : layer_add) { // cerr << it.first << " " << it.second << "\n"; // } int j = 0; for(int i = 0; i < layer_add.size(); i++){ auto [x_add, y_add] = layer_add[i]; if(A[x_add][y_add] == '*') { vis[x_add][y_add] = true; continue; } while(j < layer_del.size() && vis[layer_del[j].first][layer_del[j].second]) { j++; } assert(j < layer_del.size()); auto[x_del, y_del] = layer_del[j]; ret.push_back({x_del, y_del, x_add, y_add}); A[x_add][y_add] = '*'; A[x_del][y_del] = '.'; j++; } return ret; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> M; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { cin >> A[i][j]; } } for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { cin >> B[i][j]; } } auto path = make_path(); if(path.empty()) { cout << "NO\n"; return 0; } auto moves = move_amoeba(path); cout << "YES\n"; cout << moves.size() << "\n"; for(auto it : moves) { cout << it.a << " " << it.b << " " << it.c << " " << it.d << "\n"; } return 0; } /* 3 3 **X X.X X.. ..X X.X X** 5 8 .******. **.X**.. *******. **.X**.. .******. .******. ...X**** .******* ...X**** .******. */