#include constexpr const int di[] = { 1, -1, 0, 0 }; constexpr const int dj[] = { 0, 0, 1, -1 }; int n, m; std::vector g, h; std::vector > find_path() { std::vector >> par(n, std::vector > (m, { -1, -1 })); std::vector > vis(n, std::vector (m, false)); std::queue , std::pair >> q; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (g[i][j] == '*') { q.push({ { i, j }, { -1, -1 } }); } if (g[i][j] == 'X') { vis[i][j] = true; } } } while (q.size()) { auto [cu, pa] = q.front(); q.pop(); int i = cu.first, j = cu.second; if (vis[i][j]) continue; vis[i][j] = true; par[i][j] = pa; if (h[i][j] == '*') { // FOUND PATH std::vector > res; do { res.emplace_back(i, j); auto _pa = par[i][j]; i = _pa.first; j = _pa.second; } while (i != -1); std::reverse(res.begin(), res.end()); return res; } for (int d = 0; d < 4; d++) { int I = i + di[d]; int J = j + dj[d]; if (I < 0 || J < 0 || I >= n || J >= m) continue; q.push({ { I, J }, cu }); } } std::cout << "NO\n"; exit(0); } bool bfs() { std::queue > q; for (int i = 0; i < n && q.empty(); i++) { for (int j = 0; j < m; j++) { if (g[i][j] == '*') { q.emplace(i, j); break; } } } std::vector > vis(n, std::vector (m, false)); while (q.size()) { auto [i, j] = q.front(); q.pop(); if (g[i][j] != '*' || vis[i][j]) continue; vis[i][j] = true; for (int d = 0; d < 4; d++) { int I = i + di[d]; int J = j + dj[d]; if (I < 0 || J < 0 || I >= n || J >= m) continue; q.emplace(I, J); } } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (g[i][j] == '*' && !vis[i][j]) return false; return true; } int cnt_nei(int i, int j) { int res = 0; for (int d = 0; d < 4; d++) { int I = i + di[d]; int J = j + dj[d]; res += I >= 0 && J >= 0 && I < n && J < m && g[I][J] == '*'; } return res; } bool can_remove(int i, int j) { if (cnt_nei(i, j) == 1) return true; g[i][j] = '.'; bool res = bfs(); g[i][j] = '*'; return res; } std::vector > ban; bool spec_case = false; std::pair locate(std::pair banned) { spec_case = false; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (ban[i][j]) continue; if (i == banned.first && j == banned.second) { continue; } if (g[i][j] == '*') { if (h[i][j] == '*') continue; if (can_remove(i, j)) { return { i, j }; } } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (ban[i][j]) continue; if (h[i][j] != '*') continue; if (i == banned.first && j == banned.second) { continue; } if (g[i][j] == '*') { if (can_remove(i, j)) { spec_case = true; return { i, j }; } } } } assert(false); return { -1, -1 }; } int main() { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cin >> n >> m; ban.resize(n, std::vector< bool> (m, false)); g.resize(n); h.resize(n); for (auto& x : g) std::cin >> x; for (auto& x : h) std::cin >> x; auto path = find_path(); assert(path.size()); //for (auto p : path) std::cerr << "(" << p.first << ", " << p.second << ") "; //std::cerr << std::endl; { std::queue > q; q.emplace(path.back()); assert(h[path.back().first][path.back().second] == '*'); std::vector > vis(n, std::vector (m, false)); while (q.size()) { auto [i, j] = q.front(); q.pop(); if (h[i][j] != '*' || vis[i][j]) continue; vis[i][j] = true; path.push_back({ i, j }); for (int d = 0; d < 4; d++) { int I = i + di[d]; int J = j + dj[d]; if (I < 0 || J < 0 || I >= n || J >= m) continue; q.emplace(I, J); } } } //for (auto p : path) std::cerr << "(" << p.first << ", " << p.second << ") "; //std::cerr << std::endl; int pi = path.front().first; int pj = path.front().second; path.erase(path.begin()); std::vector > ans; std::vector > pat; while (true) { for (auto [ti, tj] : path) { if (g[ti][tj] == '*') { pi = ti; pj = tj; continue; } auto [fi, fj] = locate({ pi, pj }); g[fi][fj] = '.'; g[ti][tj] = '*'; pi = ti; pj = tj; if (spec_case) { ban[ti][tj] = true; pat.push_back({ fj, fj }); } ans.push_back({ fi, fj, ti, tj }); } if (pat.size()) { std::reverse(pat.begin(), pat.end()); path = pat; pat.clear(); } else break; } std::cout << "YES\n"; std::cout << ans.size() << "\n"; for (auto v : ans) { for (int i = 0; i < 4; i++) { std::cout << v[i] + 1 << " \n"[i == 3]; } } }