#pragma GCC optimize "O3" #include using namespace std; using LL=long long; #define FOR(i,l,r) for(int i=(l);i<=(r);++i) #define REP(i,n) FOR(i,0,(n)-1) #define ssize(x) int(x.size()) #ifdef DEBUG auto&operator<<(auto&o,pairp){return o<<"("<decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<sync_with_stdio(0); int h, w; cin >> h >> w; vector> current(w, vector(h)); vector> goal(w, vector(h)); vector> is_blocked(w, vector(h)); REP(y, h) REP(x, w) { char c; cin >> c; if(c == '*') current[x][y] = true; else if(c == 'X') is_blocked[x][y] = true; } REP(y, h) REP(x, w) { char c; cin >> c; if(c == '*') goal[x][y] = true; } debug(current, goal, is_blocked); pair start_inters = {-1, -1}; REP(x, w) REP(y, h) if(current[x][y] and goal[x][y]) start_inters = {x, y}; debug(start_inters); using P = pair; vector> out; auto add_to_out = [&](P from, P to) { debug("adding to out", from, to); assert(current[from.first][from.second]); assert(not current[to.first][to.second]); current[from.first][from.second] = false; current[to.first][to.second] = true; out.emplace_back(from, to); }; array dx = {0, 1, 0, -1}; array dy = {1, 0, -1, 0}; constexpr int sides = 4; auto is_valid = [&](int x, int y) { return 0 <= min(x, y) and x < w and y < h; }; if(start_inters.first == -1) { REP(x, w) REP(y, h) if(current[x][y]) start_inters = {x, y}; vector

current_path; vector> vis(w, vector(h)); function dfs = [&](int x, int y) { vis[x][y] = true; current_path.emplace_back(x, y); if(goal[x][y]) return true; REP(s, sides) { int xx = x + dx[s]; int yy = y + dy[s]; if(is_valid(xx, yy) and not vis[xx][yy] and not is_blocked[xx][yy]) { if(dfs(xx, yy)) return true; } } current_path.pop_back(); return false; }; if(not dfs(start_inters.first, start_inters.second)) { #ifdef LOCAL cout << "OK\n"; #else cout << "NO\n"; #endif exit(0); } debug(current_path); int last_current_in_path = 0; REP(i, ssize(current_path)) if(current[current_path[i].first][current_path[i].second]) last_current_in_path = i; { vector

new_current_path; FOR(i, last_current_in_path, ssize(current_path) - 1) new_current_path.emplace_back(current_path[i]); current_path = new_current_path; start_inters = current_path.front(); } debug(current_path); REP(x, w) REP(y, h) vis[x][y] = false; vector> order; function order_dfs = [&](int x, int y) { vis[x][y] = true; order.emplace_back(x, y); REP(s, sides) { int xx = x + dx[s]; int yy = y + dy[s]; if(is_valid(xx, yy) and not vis[xx][yy] and current[xx][yy]) { order_dfs(xx, yy); } } }; order_dfs(start_inters.first, start_inters.second); debug(order); reverse(order.begin(), order.end()); REP(i, ssize(current_path) - 1) { add_to_out(order[i], current_path[i + 1]); // HERE order.emplace_back(current_path[i + 1]); } start_inters = current_path.back(); } debug(out); debug(current); while(true) { assert(current[start_inters.first][start_inters.second] and goal[start_inters.first][start_inters.second]); vector> inters_comp(w, vector(h)); function inters_dfs = [&](int x, int y) { inters_comp[x][y] = true; REP(s, sides) { int xx = x + dx[s]; int yy = y + dy[s]; if(is_valid(xx, yy) and not inters_comp[xx][yy] and current[xx][yy] and goal[xx][yy]) { inters_dfs(xx, yy); } } }; inters_dfs(start_inters.first, start_inters.second); vector> order; vector> vis = inters_comp; function order_dfs = [&](int x, int y) { if(not inters_comp[x][y]) order.emplace_back(x, y); vis[x][y] = true; REP(s, sides) { int xx = x + dx[s]; int yy = y + dy[s]; if(is_valid(xx, yy) and not vis[xx][yy] and current[xx][yy]) order_dfs(xx, yy); } }; REP(x, w) REP(y, h) if(inters_comp[x][y]) order_dfs(x, y); if(order.empty()) { debug("finished"); break; } P removing = order.back(); debug(removing); P adding = {-1, -1}; REP(x, w) REP(y, h) if(inters_comp[x][y]) REP(s, 4) { int xx = x + dx[s]; int yy = y + dy[s]; if(is_valid(xx, yy) and goal[xx][yy] and not current[xx][yy]) adding = {xx, yy}; } debug(adding); assert(adding.first != -1); add_to_out(removing, adding); } assert(current == goal); #ifdef LOCAL cout << "OK\n"; #else cout << "YES\n"; cout << ssize(out) << '\n'; for(auto [from, to] : out) cout << from.first + 1 << ' ' << from.second + 1 << ' ' << to.first + 1 << ' ' << to.second + 1 << '\n'; #endif }