#include using namespace std; typedef pair pii; int n, m; vector adj = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} }; void dfs(int i, int j, vector> &used, vector &board, vector &out_order, bool add_used = false) { // if (add_used) out_order.push_back({i, j}); used[i][j] = true; for (auto [di, dj] : adj) { int ni = i + di; int nj = j + dj; if (ni < 0 || nj < 0) continue; if (ni >= n || nj >= m) continue; // go to the child if (used[ni][nj]) continue; if (board[ni][nj] != '*') continue; dfs(ni, nj, used, board, out_order); } } bool dfs2(int i, int j, vector> &used, vector &target, deque &out_order) { used[i][j] = true; for (auto [di, dj] : adj) { int ni = i + di; int nj = j + dj; if (ni < 0 || nj < 0) continue; if (ni >= n || nj >= m) continue; // go to the child if (used[ni][nj]) continue; if (target[ni][nj] == 'X') continue; if (target[ni][nj] == '*') { // FOUND! out_order.push_front({ni, nj}); out_order.push_front({i, j}); return true; } bool found = dfs2(ni, nj, used, target, out_order); if (found) { out_order.push_front({i, j}); return true; } } return false; } int main() { cin.tie(nullptr); cout.tie(nullptr); iostream::sync_with_stdio(false); cin >> n >> m; vector start(n), target(n); for (int i = 0; i < n; i++) cin >> start[i]; for (int i = 0; i < n; i++) cin >> target[i]; // Check intersection set inter; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (start[i][j] == '*' && target[i][j] == '*') inter.insert({i, j}); } } vector> answer; if (!inter.empty()) { // Intersection is not empty // BUILD ORDER 1 vector order1; vector> used(n, vector(m)); for (auto [i, j] : inter) used[i][j] = true; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (start[i][j] != '*') continue; bool has_inter_adj = false; for (auto [di, dj] : adj) { int ni = i + di; int nj = j + dj; if (ni < 0 || nj < 0) continue; if (ni >= n || nj >= m) continue; if (inter.count({ni, nj})) has_inter_adj = true; } if (has_inter_adj && !used[i][j]) dfs(i, j, used, start, order1); } } // BUILD ORDER 2 vector order2; used = vector>(n, vector(m)); for (auto [i, j] : inter) used[i][j] = true; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (target[i][j] != '*') continue; bool has_inter_adj = false; for (auto [di, dj] : adj) { int ni = i + di; int nj = j + dj; if (ni < 0 || nj < 0) continue; if (ni >= n || nj >= m) continue; if (inter.count({ni, nj})) has_inter_adj = true; } if (has_inter_adj && !used[i][j]) dfs(i, j, used, target, order2); } } assert(order1.size() == order2.size()); // GO ORDER for (int i = 0; i < order1.size(); i++) { answer.push_back({order1[order1.size() - 1 - i], order2[i]}); } // DONE, sosi huy } else { // INTERSECTION IS EMPTY // FIND PATH from start to target deque path; vector> used(n, vector(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (start[i][j] != '*') continue; used[i][j] = true; } } bool found = false; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (start[i][j] != '*') continue; found = dfs2(i, j, used, target, path); if (found) break; } if (found) break; } if (!found) { cout << "NO\n"; exit(0); } // PATH FOUND pii start_anchor = path.front(); path.pop_front(); pii target_anchor = path.back(); path.pop_back(); // BUILD ORDERS for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { used[i][j] = false; } } vector _order1, _order2; dfs(start_anchor.first, start_anchor.second, used, start, _order1); dfs(target_anchor.first, target_anchor.second, used, target, _order2); deque order1(_order1.begin(), _order1.end()); deque order2(_order2.begin(), _order2.end()); while (!path.empty()) { auto mid = path.front(); path.pop_front(); auto e1 = order1.back(); order1.pop_back(); order1.push_front(mid); answer.emplace_back(e1, mid); } for (int i = 0; i < order1.size(); i++) { answer.push_back({order1[order1.size() - 1 - i], order2[i]}); } } // WRITE ANSWER cout << "YES\n"; cout << answer.size() << '\n'; assert(answer.size() < 10000); for (auto [from, to] : answer) { cout << from.first + 1 << ' ' << from.second + 1 << ' ' << to.first + 1 << ' ' << to.second + 1 << '\n'; } }