#include using namespace std; typedef long long ll; static constexpr int MAXR = 55; static int R, C; static char A[MAXR][MAXR], B[MAXR][MAXR]; static int dist[MAXR][MAXR]; static bool vis[MAXR][MAXR]; static vector> moves; static constexpr int dx[] = {0, 0, 1, -1}; static constexpr int dy[] = {1, -1, 0, 0}; static void precalc() { memset(dist, 0x3f, sizeof(dist)); queue> Q; for (int x = 0; x < R; x++) { for (int y = 0; y < C; y++) { if (B[x][y] == '*') Q.emplace(0, x, y); } } while (!Q.empty()) { auto [d, x, y] = Q.front(); Q.pop(); if (vis[x][y]) continue; vis[x][y] = true; dist[x][y] = d; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= R || ny >= C || vis[nx][ny]) continue; if (A[nx][ny] == 'X') continue; Q.emplace(d + 1, nx, ny); } } } static pair move1() { tuple S = {1e9, 0, 0}; for (int x = 0; x < R; x++) { for (int y = 0; y < C; y++) { if (A[x][y] == '*') S = min(S, {dist[x][y], x, y}); } } for (int x = 0; x < R; x++) { for (int y = 0; y < C; y++) { if (A[x][y] == '*') { for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= R || ny >= C || A[nx][ny] != '.') continue; S = min(S, {dist[nx][ny], nx, ny}); } } } } auto [d, x, y] = S; if (d == 0) return {x, y}; if (A[x][y] == '*') return {-1, -1}; memset(vis, 0, sizeof(vis)); priority_queue> Q; Q.emplace(0, x, y); int lx = -1, ly = -1; while (!Q.empty()) { auto [d, x, y] = Q.top(); Q.pop(); if (vis[x][y]) continue; vis[x][y] = true; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= R || ny >= C || vis[nx][ny]) continue; if (A[nx][ny] != '*') { continue; } Q.emplace(-dist[nx][ny], nx, ny); } } assert (lx != -1 && ly != -1); moves.emplace_back(lx, ly, x, y); A[lx][ly] = '.'; A[x][y] = '*'; return {x, y}; } static bool move2(int sx, int sy) { memset(vis, 0, sizeof(vis)); priority_queue> Q; Q.emplace(0, sx, sy); int rx = -1, ry = -1; int lx = -1, ly = -1; while (!Q.empty()) { auto [d, x, y] = Q.top(); Q.pop(); if (vis[x][y]) continue; vis[x][y] = true; lx = x; ly = y; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= R || ny >= C || vis[nx][ny]) continue; if (A[nx][ny] != '*') { if (B[nx][ny] == '*' && rx == -1) { rx = nx; ry = ny; } continue; } Q.emplace(-dist[nx][ny], nx, ny); } } if (rx == -1) return false; assert (lx != sx || ly != sy); assert (lx != -1 && ly != -1); moves.emplace_back(lx, ly, rx, ry); A[lx][ly] = '.'; A[rx][ry] = '*'; return true; } static void solve() { cin >> R >> C; for (int i = 0; i < R; i++) { cin >> A[i]; } for (int i = 0; i < R; i++) { cin >> B[i]; } precalc(); int x = 0, y = 0; for (;;) { tie(x, y) = move1(); if (x == -1) { cout << "NO\n"; return; } if (dist[x][y] == 0) break; #if DEBUG for (int x = 0; x < R; x++) { cout << A[x] << endl; } cout << endl; #endif } while (move2(x, y)) { #if DEBUG for (int x = 0; x < R; x++) { cout << A[x] << endl; } cout << endl; #endif } cout << "YES\n"; for (auto [a, b, c, d] : moves) { cout << a << ' ' << b << ' ' << c << ' ' << d << '\n'; } } int main() { ios::sync_with_stdio(false); int T = 1; // cin >> T; for (int i = 1; i <= T; i++) { solve(); } return 0; }