// Saarland University: <(OvO)> #include #define sz(a) ((int)(a).size()) #define divceil(a, b) ((a) + (b) - 1) / (b) using namespace std; #ifdef ONPC string to_string(const char* s) { return s; } template string to_string(const T& cont) { string ans = ""; for (bool fst = true; const auto& val: cont) { if (!fst) { ans += ", "; } ans += to_string(val); fst = false; } return ans + "}"; } void debug_print_collection() { cerr << endl; } template void debug_print_collection(First val, Args... args) { cerr << " " << to_string(val); debug_print_collection(args...); } #define debug(...) { cerr << "@@@ [" << #__VA_ARGS__ << "] ="; debug_print_collection(__VA_ARGS__);} #else #define debug(...) ; #define NDEBUG #endif mt19937 rnd(123); typedef long long ll; typedef long double ld; char c[55][55]; int ok[55][55]; int n, m; const int N = 100*100; int used[N]; int tin[N]; int fup[N]; int artc[N]; vector g[N]; int timer = 0; void dfs(int v, int p = -1) { used[v] = true; tin[v] = fup[v] = timer++; int children = 0; for(int i = 0; i < sz(g[v]); i ++) { int to = g[v][i]; if(to == p) continue; if(used[to]) { fup[v] = min(fup[v], tin[to]); } else { dfs(to, v); fup[v] = min(fup[v], fup[to]); if(fup[to] >= tin[v] && p != -1) artc[v] = 1; children ++; } } if (p == -1 && children > 1) artc[v] = 1; } int who[100][100]; pair nwho[N]; int art[100][100]; void find_articulations() { timer = 0; for(int i = 0; i <= n * m + 5; i ++) { used[i] = tin[i] = fup[i] = 0; artc[i] = 0; nwho[i] = {0, 0}; g[i].clear(); } for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) art[i][j] = 0; int id = 0; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(c[i][j] == '*') { who[i][j] = ++ id; nwho[id] = {i, j}; } } } for(int i = 1; i <= n; i ++) { for(int j = 1 ; j <= m; j ++) { if(c[i][j] == '*') { int cur = who[i][j]; for(int dx = -1; dx <= 1; dx ++) for(int dy = -1; dy <= 1; dy ++) { if(abs(dx - dy) == 1 && c[i + dx][j + dy] == '*') { int next = who[i + dx][j + dy]; g[cur].push_back(next); // g[next].push_back(cur); } } } } } // cout << "art\n"; // for(int i = 1; i <= id; i ++) // { // if(g[i].size()) // { // cout << i << '\n'; // for(int x : g[i]) // cout << x << ' '; // cout << '\n'; // } // } dfs(1); for(int i = 1; i <= id; i ++) { if(artc[i]) { // cout << i << '\n'; int x = nwho[i].first, y = nwho[i].second; art[x][y] = 1; } } // cout << "------\n"; } int dis[123][123]; void compute_dis() { for(int i = 0; i <= n + 1; i ++) { for(int j = 0; j <= m + 1; j ++) dis[i][j] = -1; } queue > q; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(ok[i][j]) { q.push({i, j}); dis[i][j] = 0; } } } while(q.size()) { int ux = q.front().first, uy = q.front().second; q.pop(); for(int dx = -1; dx <= 1; dx ++) { for(int dy = -1; dy <= 1; dy ++) { if(abs(dx - dy) == 1 && c[ux + dx][uy + dy] != 'X' && dis[ux + dx][uy + dy] == -1) { q.push({ux + dx, uy + dy}); dis[ux + dx][uy + dy] = dis[ux][uy] + 1; } } } } } pair findSource() { find_articulations(); compute_dis(); int ansX = 0, ansY = 0, mx = -1; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(c[i][j] != '*' || art[i][j] || ok[i][j]) continue; if(dis[i][j] != -1 && dis[i][j] > mx) { mx = dis[i][j]; ansX = i; ansY = j; } } } return {ansX, ansY}; } bool isAdjacent(int x, int y) { for(int dx = -1; dx <= 1; dx ++) { for(int dy = -1; dy <= 1; dy ++) { if(abs(dx - dy) == 1 && c[x + dx][y + dy] == '*') { return true; } } } return false; } pair findDest() { compute_dis(); int ansX = -1, ansY = -1, mn = 1e9; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(c[i][j] == '.' && isAdjacent(i, j)) { //not sure if(dis[i][j] != -1 && dis[i][j] < mn) { mn = dis[i][j]; ansX = i; ansY = j; } } } cout << "NO\n"; } return {ansX, ansY}; } int solve() { if (!(cin >> n >> m)) { return 1; } for(int i = 0; i <= n + 1; i ++) { for(int j = 0; j <= m + 1; j ++) { c[i][j] = 'X'; ok[i][j] = 0; } } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) cin >> c[i][j]; } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { char x; cin >> x; if(x == '*') ok[i][j] = 1; } } int sX, sY, dX, dY; vector > ans; do { pair pff = findSource(); sX = pff.first; sY = pff.second; c[sX][sY] = '.'; pff = findDest(); dX = pff.first; dY = pff.second; c[dX][dY] = '*'; if(dX != -1 || sX != 0) ans.push_back({sX, sY, dX, dY}); // cout << sX << ' ' << sY << ' ' << dX << ' ' << dY << '\n'; // for(int i = 1; i <= n; i++, cout << '\n') // for(int j = 1; j <= m; j ++) // cout << art[i][j]; // cout << '\n'; int ff = 1; for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { if(ok[i][j] && c[i][j] != '*') { ff = 0; break; } if(ff == 1) break; } }while(dX != -1 && sX != 0); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) { if(ok[i][j] && c[i][j] != '*') { cout << "NO\n"; return 0; } } cout << "YES\n"; cout << ans.size() << '\n'; for(auto x : ans) { for(int i : x) cout << i << ' '; cout << '\n'; } return 0; } int32_t main() { #ifdef ONPC assert(freopen("J.txt", "r", stdin)); #endif ios::sync_with_stdio(0); cin.tie(0); int TET = 1e9; // cin >> TET; for (int i = 1; i <= TET; i ++) { if (solve()) { break; } #ifdef ONPC cout << "__________________" << endl; #endif } #ifdef ONPC cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; #endif } /* g++ -std=c++20 -Wall -Wextra -Wshadow -D_GLIBCXX_DEBUG -DONPC -O2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -o ex template.cpp && ./ex */