//#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx2,tune=native") #include using namespace std; const int K = 4; const int dx[K] = { 1, -1, 0, 0 }; const int dy[K] = { 0, 0, 1, -1 }; const int N = 55; char a[N][N]; char b[N][N]; int dist[N][N]; int n, m; bool valid(int i, int j) { return i >= 0 && i < n && j >= 0 && j < m && a[i][j] != 'X'; } int used[N][N]; void dfs(int i, int j) { used[i][j] = 1; for (int k = 0; k < K; ++k) { int ni = i+dx[k]; int nj = j+dy[k]; if (valid(ni, nj) && a[i][j] == '*' && !used[ni][nj]) dfs(ni, nj); } } bool can_remove(int i, int j) { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) used[i][j] = 0; int gi, gj; for (int k = 0; k < K; ++k) { int ni = i+dx[k]; int nj = j+dy[k]; if (valid(ni, nj) && a[ni][nj] == '*') { gi = ni; gj = nj; } } a[i][j] = '.'; dfs(gi, gj); a[i][j] = '*'; for (int k = 0; k < K; ++k) { int ni = i+dx[k]; int nj = j+dy[k]; if (valid(ni, nj) && a[ni][nj] == '*') { if (!used[ni][nj]) return false; } } return true; } bool can_add(int i, int j) { for (int k = 0; k < K; ++k) { int ni = i+dx[k]; int nj = j+dy[k]; if (valid(ni, nj) && a[ni][nj] == '*') return true; } return false; } void printa() { for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cout << a[i][j]; } cout << '\n'; } cout << '\n'; } int good[N][N]; void dfs2(int i, int j) { good[i][j] = 1; for (int k = 0; k < K; ++k) { int ni = i+dx[k]; int nj = j+dy[k]; if (valid(ni, nj) && a[ni][nj] == '*' && b[ni][nj] == '*' && !good[ni][nj]) dfs2(ni, nj); } } bool can_add_good(int i, int j) { for (int k = 0; k < K; ++k) { int ni = i+dx[k]; int nj = j+dy[k]; if (valid(ni, nj) && good[ni][nj] && b[i][j] == '*') return true; } return false; } pair dfs3(int i, int j) { used[i][j] = 1; pair ret = {i, j}; for (int k = 0; k < K; ++k) { int ni = i+dx[k]; int nj = j+dy[k]; if (valid(ni, nj) && a[ni][nj] == '*' && !used[ni][nj]) ret = dfs3(ni, nj); } return ret; } int main() { //cin.tie(0); //ios_base::sync_with_stdio(false); // cin >> n >> m; int dia, dja; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> a[i][j]; dist[i][j] = -1; if (a[i][j] == '*') { dia = i; dja = j; } } } int di, dj; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> b[i][j]; dist[i][j] = -1; if (b[i][j] == '*') { di = i; dj = j; } } } // BFS desde di dj queue> q; q.push({di, dj}); dist[di][dj] = 0; while (!q.empty()) { int cx = q.front().first; int cy = q.front().second; q.pop(); for (int k = 0; k < K; ++k) { int nx = cx+dx[k]; int ny = cy+dy[k]; if (!valid(nx, ny)) continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[cx][cy]+1; q.push({nx, ny}); } } // Caso malo (único) while (dist[dia][dja] == -1) { cout << "NO\n"; return 0; } // Fase 1 int it1 = 0; vector, pair>> ops; while (a[di][dj] != '*') { int ei, ej; int ed = 1e9; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == '*' && dist[i][j] < ed) { ei = i; ej = j; ed = dist[i][j]; } } } for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { used[i][j] = 0; } pair rr = dfs3(ei, ej); ei = rr.first; ej = rr.second; a[ei][ej] = '.'; //printa(); int fi, fj; int fd = 1e9; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == '.' && can_add(i, j) && dist[i][j] < fd) { fi = i; fj = j; fd = dist[i][j]; } } } a[fi][fj] = '*'; ops.push_back({{ei, ej}, {fi, fj}}); //printa(); ++it1; if (it1 >= 50*50*5) assert(false); } // Fase 250*50 int it2 = 0; while (true) { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) good[i][j] = 0; dfs2(di, dj); int ei = -1, ej; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { dist[i][j] = -1; if (!good[i][j] && a[i][j] == '*') { ei = i; ej = j; } } } if (ei == -1) break; // queue> q; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { if (good[i][j]) { dist[i][j] = 0; q.push({i, j}); } } while (!q.empty()) { int cx = q.front().first; int cy = q.front().second; ei = cx; ej = cy; q.pop(); for (int k = 0; k < K; ++k) { int nx = cx+dx[k]; int ny = cy+dy[k]; if (!valid(nx, ny) || a[nx][ny] != '*') continue; if (dist[nx][ny] != -1) continue; dist[nx][ny] = dist[cx][cy]+1; q.push({nx, ny}); } } // a[ei][ej] = '.'; int fi, fj; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == '.' && can_add_good(i, j)) { fi = i; fj = j; } } } a[fi][fj] = '*'; ops.push_back({{ei, ej}, {fi, fj}}); //printa(); ++it2; if (it2 >= 50*50*5) assert(false); } cout << "YES\n"; cout << ops.size() << '\n'; for (auto co : ops) { cout << co.first.first+1 << ' ' << co.first.second+1 << ' ' << co.second.first+1 << ' ' << co.second.second+1 << '\n'; } //printa(); }