#include #define pii pair #define x first #define y second using namespace std; struct S { pii from, to; }; int n, m; constexpr int dx[4] = {-1, 0, 1, 0}; constexpr int dy[4] = {0, 1, 0, -1}; string a[55], b[55]; int dp[55][55]; pii lst[55][55]; set all; vector ans; bool can_delete(pii p2) { queue q; set temp = all; temp.erase(p2); vector > viz(n + 1); a[p2.x][p2.y] = '.'; q.push({*temp.begin()}); for(int i = 0; i <= n; i++) viz[i].resize(m + 1); int cnt = 0; while(!q.empty()) { pii p = q.front(); q.pop(); int x = p.x, y = p.y; //cerr << x << " " << y << " sclavie\n"; for(int d = 0; d < 4; d++) { int i = x + dx[d], j = y + dy[d]; if(1 <= i && i <= n && 1 <= j && j <= m && !viz[i][j] && a[i][j] == '*') { viz[i][j] = 1; cnt++; q.push({i, j}); } } } bool ok = (cnt == temp.size()); //all.insert(p); a[p2.x][p2.y] = '*'; //cerr << "fmm\n"; return ok; } void solve() { srand(time(0)); cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i], a[i] = '#' + a[i]; } cin >> ws; for(int i = 1; i <= n; i++) { cin >> b[i], b[i] = '#' + b[i]; } queue q; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { dp[i][j] = 1e9; if(b[i][j] == '*') q.push({i, j}), dp[i][j] = 0; if(a[i][j] == '*') all.insert({i, j}); } } while(!q.empty()) { pii p = q.front(); q.pop(); int x = p.x, y = p.y; for(int d = 0; d < 4; d++) { int i = x + dx[d], j = y + dy[d]; if(b[i][j] == '.' && 1 <= i && i <= n && 1 <= j && j <= m && dp[i][j] > dp[x][y] + 1) { dp[i][j] = dp[x][y] + 1; q.push({i, j}); } } } while(ans.size() < 10000) { int mx = -1e9; pii p = {0, 0}; for(auto &poz : all) { //cout << poz.x << " " << poz.y << " " << can_delete(poz) << "\n"; if(can_delete(poz) && dp[poz.x][poz.y] > mx) { mx = dp[poz.x][poz.y]; //cout << poz.x << " " << poz.y << " " << mx << "\n"; p = poz; } } if(mx == 0) { cout << "YES\n"; cout << ans.size() << "\n"; for(auto &[p1, p2] : ans) { cout << p1.x << " " << p1.y << " " << p2.x << " " << p2.y << "\n"; } return; } int mn = 1e9; vector all_poz; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(a[i][j] == '.') { bool has_neigh = 0; for(int d = 0; d < 4; d++) { int x = i + dx[d], y = j + dy[d]; if(1 <= x && x <= n && 1 <= y && y <= m && a[x][y] == '*') has_neigh = 1; } if(has_neigh) { if(dp[i][j] < mn) { mn = dp[i][j]; all_poz.clear(); all_poz.push_back({i, j}); } else if(dp[i][j] == mn) all_poz.push_back({i, j}); } } } } pii p2 = all_poz[rand() % all_poz.size()]; ans.push_back({p, p2}); all.erase(p); all.insert(p2); a[p.x][p.y] = '.'; a[p2.x][p2.y] = '*'; } cout << "NO\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("test.in", "r", stdin); freopen("test.out", "w", stdout); #else #endif int T = 1; //cin >> T; while(T--) { solve(); } return 0; }