#include using namespace std; const int maxn = 50; bool wall[50][50], A[maxn][maxn], B[maxn][maxn]; int r, c; bool ok(int i, int j){ return 0 <= i && i < r && 0 <= j && j < c; } bool is_wall(int i, int j) { return !ok(i, j) || wall[i][j]; } bool is_a(int i, int j) { return ok(i, j) && A[i][j]; } bool is_b(int i, int j) { return ok(i, j) && B[i][j]; } pair dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; pair bfs_a(const vector> &start){ vector> vis(r, vector(c, false)); vector> q = start; for(auto [x, y] : start) vis[x][y] = true; for(int i = 0; i < (int)q.size(); i++){ int x = q[i].first; int y = q[i].second; for(auto [dx, dy] : dir){ int nx = x + dx; int ny = y + dy; if(is_a(nx, ny) && !vis[nx][ny]){ vis[nx][ny] = true; q.emplace_back(nx, ny); } } } return q.back(); } struct mozg{ int x1, y1, x2, y2; }; vector mozog; void do_move(const vector>& fixed, pair nxt){ // cout << "do move" << '\n'; // for(int i = 0; i < r; i++){ // for(int j = 0; j < c; j++){ // if(is_a(i, j)) cout << '*'; // else cout << ' '; // } // cout << '\n'; // } if(is_a(nxt.first, nxt.second)) return; auto res = bfs_a(fixed); A[res.first][res.second] = false; A[nxt.first][nxt.second] = true; // cout << "fixed: "; // for(auto [x, y] : fixed) cout << x << ' ' << y << '\n'; // cout << "move\n"; // cout << res.first + 1 << ' ' << res.second + 1 << '\n'; // cout << nxt.first + 1 << ' ' << nxt.second + 1 << ' ' << is_a(nxt.first, nxt.second) << '\n'; mozog.push_back({res.first, res.second, nxt.first, nxt.second}); } void solve1(pair start){ // cout << start.first << ' ' << start.second << '\n'; vector> vis(r, vector(c, false)); vector> fixed = {start}, q = {start}; vis[start.first][start.second] = true; for(int i = 0; i < (int)q.size(); i++){ int x = q[i].first; int y = q[i].second; // cout << "curr: " << x + 1<< ' ' << y + 1 << '\n'; if(i > 0){ do_move(fixed, q[i]); fixed.push_back(q[i]); } for(auto [dx, dy] : dir){ int nx = x + dx; int ny = y + dy; if(is_b(nx, ny) && !vis[nx][ny]){ vis[nx][ny] = true; q.emplace_back(nx, ny); } } } } int solve_path(int sx, int sy){ const int inf = 1e9; vector> dist(r, vector(c,inf)); vector> q = {{sx, sy}}; dist[sx][sy] = 0; for(int i = 0; i < (int)q.size(); i++){ int x = q[i].first; int y = q[i].second; for(auto [dx, dy] : dir){ int nx = x + dx; int ny = y + dy; if(!is_wall(nx, ny) && dist[nx][ny] == inf){ dist[nx][ny] = dist[x][y] + 1; q.emplace_back(nx, ny); } } } pair tmp = {-1, -1}; int best = inf; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ if(is_a(i, j) && dist[i][j] < best){ best = dist[i][j]; tmp = {i, j}; } } } if(tmp.first == -1) return -1; if(best == 0) return 1; for(auto [dx, dy] : dir){ int nx = tmp.first + dx; int ny = tmp.second + dy; if(!is_wall(nx, ny) && dist[nx][ny] < best){ do_move({tmp}, {nx, ny}); break; } } return 0; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>r>>c; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ char c; cin>>c; if(c == 'X') wall[i][j] = true; if(c == '*') A[i][j] = true; } } int sx, sy; for(int i = 0; i < r; i++){ for(int j = 0; j < c; j++){ char c; cin>>c; if(c == '*') { B[i][j] = true; sx = i; sy = j; } } } int res = solve_path(sx, sy); if(res == -1){ cout << "NO\n"; return 0; } while(res != 1) res = solve_path(sx, sy); solve1({sx, sy}); cout << "YES\n"; cout << mozog.size() << '\n'; for(auto m : mozog){ cout << m.x1 + 1 << ' ' << m.y1 + 1 << ' ' << m.x2 + 1 << ' ' << m.y2 + 1 << '\n'; } return 0; }