#include "bits/stdc++.h" using namespace std; using LL = long long; using ll = long long; #define all(x) begin(x),end(x) const int MAXN = 50; using pt = pair < int , int >; bool ostacolo[MAXN][MAXN]; bool prima_ameba[MAXN][MAXN]; int prima_ameba_id[MAXN][MAXN]; bool seconda_ameba[MAXN][MAXN]; int seconda_ameba_id[MAXN][MAXN]; bool vis[MAXN][MAXN]; pt par[MAXN][MAXN]; int main() { // ios_base::sync_with_stdio(false); // cin.tie(NULL); int N, M; cin >> N >> M; auto in_mat = [&] (int i, int j) -> bool { return 0 <= i && i < N && 0 <= j && j < M; }; queue < pt > q; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { char c; cin >> c; if (c == '*') { prima_ameba[i][j] = true; q.emplace(i, j); par[i][j] = make_pair(i, j); vis[i][j] = true; } if (c == 'X') ostacolo[i][j] = true; } for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { char c; cin >> c; if (c == '*') seconda_ameba[i][j] = true; if (c == 'X') ostacolo[i][j] = true; } pt intersect; bool exists = false; while(!q.empty()) { auto [i, j] = q.front(); q.pop(); if (seconda_ameba[i][j]) { intersect = make_pair(i, j); exists = true; break; } for (int d = -1; d <= 1; d += 2) { if (in_mat(i+d, j) && !vis[i+d][j]) { par[i+d][j] = make_pair(i, j); vis[i+d][j] = true; q.emplace(i+d, j); } if (in_mat(i, j+d) && !vis[i][j+d]) { par[i][j+d] = make_pair(i, j); vis[i][j+d] = true; q.emplace(i, j+d); } } } if (!exists) { cout << "NO\n"; exit(0); } bool entered = false; while(q.size()) q.pop(); q.push(intersect); prima_ameba_id[intersect.first][intersect.second] = 1; int cur = 1; while(!q.empty()) { auto [i, j] = q.front(); q.pop(); if (!entered && prima_ameba[i][j]) { entered = true; intersect = make_pair(i, j); } for (int d = -1; d <= 1; d += 2) { int ni = i+d, nj = j; if (in_mat(ni, nj) && prima_ameba_id[ni][nj] == 0 && (prima_ameba[ni][nj] || par[i][j] == make_pair(ni, nj))) { q.emplace(ni, nj); prima_ameba_id[ni][nj] = cur++; } ni = i, nj = j+d; if (in_mat(ni, nj) && prima_ameba_id[ni][nj] == 0 && (prima_ameba[ni][nj] || par[i][j] == make_pair(ni, nj))) { q.emplace(ni, nj); prima_ameba_id[ni][nj] = cur++; } } } q.emplace(intersect); seconda_ameba_id[intersect.first][intersect.second] = 1; cur = 1; while(!q.empty()) { auto [i, j] = q.front(); q.pop(); if (!entered && seconda_ameba[i][j]) { entered = true; intersect = make_pair(i, j); } for (int d = -1; d <= 1; d += 2) { int ni = i+d, nj = j; if (in_mat(ni, nj) && seconda_ameba_id[ni][nj] == 0 && (seconda_ameba[ni][nj] || (prima_ameba_id[i][j] != 0 && !prima_ameba[i][j]))) { seconda_ameba_id[ni][nj] = cur++; q.emplace(ni, nj); } ni = i, nj = j+d; if (in_mat(ni, nj) && seconda_ameba_id[ni][nj] == 0 && (seconda_ameba[ni][nj] || (prima_ameba_id[i][j] != 0 && !prima_ameba[i][j]))) { seconda_ameba_id[ni][nj] = cur++; q.emplace(ni, nj); } } } pt prima_ameba_con_id[N*M+100]; fill(prima_ameba_con_id, prima_ameba_con_id+N*M+100, make_pair(-1, -1)); pt seconda_ameba_con_id[N*M+100]; fill(seconda_ameba_con_id, seconda_ameba_con_id+N*M+100, make_pair(-1, -1)); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) { if (prima_ameba_id[i][j] != 0) prima_ameba_con_id[prima_ameba_id[i][j]] = make_pair(i, j); if (seconda_ameba_id[i][j] != 0) seconda_ameba_con_id[seconda_ameba_id[i][j]] = make_pair(i, j); } vector < pair < pt, pt > > ans; int seconda_ameba_libero = 1; for (int id = N*M+99; id >= 1; id --) { if (prima_ameba_con_id[id] == make_pair(-1, -1)) continue; pt da_spostare = prima_ameba_con_id[id]; int id2 = seconda_ameba_id[da_spostare.first][da_spostare.second]; pt target = seconda_ameba_con_id[seconda_ameba_libero]; if (target.first == -1 && target.second == -1) break; while(prima_ameba[target.first][target.second]) { seconda_ameba_libero++; target = seconda_ameba_con_id[seconda_ameba_libero]; if (target.first == -1 && target.second == -1) break; } if (target.first == -1 && target.second == -1) { break; } if (id2 < seconda_ameba_libero && id2 != 0) { continue; } prima_ameba[da_spostare.first][da_spostare.second] = false; prima_ameba[target.first][target.second] = true; ans.emplace_back(da_spostare, target); } cout << "YES\n"; cout << ans.size() << "\n"; for (auto [a, b] : ans) { cout << a.first+1 << " " << a.second+1 << " " << b.first+1 << " " << b.second+1 << "\n"; } }