#include #define all(a) a.begin(),a.end() #define len(a) (int)(a.size()) #define fir first #define sec second #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; typedef pair pii; typedef long long ll; typedef long double ld; template bool umin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; } template bool umax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; } #ifdef KIVI #define DEBUG for (int _____DEBUG=1;_____DEBUG;_____DEBUG=0) #define LOG(...) prnt(#__VA_ARGS__" ::",__VA_ARGS__)< auto &prnt(Ts ...ts) { return ((cerr << ts << " "), ...); } #else #define DEBUG while (false) #define LOG(...) #endif const int max_n = 51, inf = 1000111222; char A[max_n][max_n], B[max_n][max_n]; struct mqueue { pair q[max_n * max_n]; int l = 0, r = 0; void clear() { l = 0, r = 0; } pair get() { return q[l++]; } void push(pii x) { q[r++] = x; } bool empty() { return (l == r); } }; mqueue q; int dist_init[max_n][max_n]; int have_cur[max_n][max_n]; pii pr_init[max_n][max_n]; bool fix[max_n][max_n]; void inline have_cur_clear() { for(int i = 0; i < max_n; i++) for(int j = 0; j < max_n; j++) have_cur[i][j] = -1; } const bool DBG = false; void solve() { vector > ans; int r, c; if(!DBG) { cin >> r >> c; for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) cin >> A[i][j]; for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) cin >> B[i][j]; } else { r = c = 50; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) A[i][j] = B[i][j] = '.'; A[0][0] = A[0][1] = '*'; B[r - 1][c - 1] = B[r - 2][c - 1] = '*'; } q.clear(); for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(B[i][j] == '*') { q.push({i, j}); dist_init[i][j] = 0; } else dist_init[i][j] = -1; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; while(!q.empty()) { auto cr = q.get(); int x = cr.fi, y = cr.se; int cdist = dist_init[x][y]; for(int mv = 0; mv < 4; mv++) { int nx = x + dx[mv], ny = y + dy[mv]; if(nx >= 0 && nx < r && ny >= 0 && ny < c && B[nx][ny] == '.' && dist_init[nx][ny] == -1) { pr_init[nx][ny] = {x, y}; dist_init[nx][ny] = cdist + 1; q.push({nx, ny}); } } } pii closest = pii{0, 0}; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(A[i][j] == '*') closest = {i, j}; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(A[i][j] == '*' && dist_init[closest.fi][closest.se] > dist_init[i][j]) closest = pii{i, j}; if(dist_init[closest.fi][closest.se] == -1) { cout << "NO\n"; return; } if(dist_init[closest.fi][closest.se] != 0) { int X = closest.fi, Y = closest.se; vector > path; int cdist = dist_init[X][Y]; path.pb({X, Y}); while(cdist--) { int NX = pr_init[X][Y].fi, NY = pr_init[X][Y].se; path.pb({NX, NY}); X = NX; Y = NY; } for(int i = 0; i + 1 < len(path); i++) { X = path[i].fi, Y = path[i].se; have_cur_clear(); have_cur[X][Y] = true; q.clear(); pii lst = {-1, -1}; q.push({X, Y}); while(!q.empty()) { auto cr = q.get(); lst = cr; int x = cr.fi, y = cr.se; for(int mv = 0; mv < 4; mv++) { int nx = x + dx[mv], ny = y + dy[mv]; if(nx >= 0 && nx < r && ny >= 0 && ny < c && A[nx][ny] == '*' && have_cur[nx][ny] == -1) { have_cur[nx][ny] = 1; q.push({nx, ny}); } } } ans.pb({lst.fi, lst.se, path[i + 1].fi, path[i + 1].se}); A[lst.fi][lst.se] = '.'; A[path[i + 1].fi][path[i + 1].se] = '*'; } } closest = pii{0, 0}; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(A[i][j] == '*') closest = {i, j}; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(A[i][j] == '*' && dist_init[closest.fi][closest.se] > dist_init[i][j]) closest = pii{i, j}; int to_fix = 0; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) to_fix += (A[i][j] == '*'); fix[closest.fi][closest.se] = true; to_fix--; int SX = closest.fi, SY = closest.se; while(to_fix) { array cur_move; q.clear(); have_cur_clear(); have_cur[SX][SY] = true; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(fix[i][j]) { have_cur[i][j] = 0; q.push({i, j}); } pair lst = {-1, -1}; pair free_fix = {-1, -1}; pair unfixed_neigh = pii{-1, -1}; while(!q.empty()) { auto cr = q.get(); lst = cr; int x = cr.fi, y = cr.se; for(int mv = 0; mv < 4; mv++) { int nx = x + dx[mv], ny = y + dy[mv]; if(nx >= 0 && nx < r && ny >= 0 && ny < c) { if(A[nx][ny] == '*' && have_cur[nx][ny] == -1) { have_cur[nx][ny] = have_cur[x][y] + 1; q.push({nx, ny}); } if(A[nx][ny] == '*' && B[nx][ny] == '*' && fix[x][y] && !fix[nx][ny]) free_fix = {nx, ny}; if(A[nx][ny] == '.' && B[nx][ny] == '*' && fix[x][y] && !fix[nx][ny]) unfixed_neigh = {nx, ny}; } } } if(free_fix != pii{-1, -1}) { to_fix--; fix[free_fix.fi][free_fix.se] = true; } else { to_fix--; fix[unfixed_neigh.fi][unfixed_neigh.se] = true; ans.pb({lst.fi, lst.se, unfixed_neigh.fi, unfixed_neigh.se}); A[lst.fi][lst.se] = '.'; A[unfixed_neigh.fi][unfixed_neigh.se] = '*'; } } cout << "YES\n"; cout << len(ans) << '\n'; for(auto& x : ans) { for(int i = 0; i < 4; i++) cout << x[i] + 1 << ' '; cout << '\n'; } // for(int i = 0; i < r; i++) { // for (int j = 0; j < c; j++) cout << A[i][j]; // cout << '\n'; // } } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; while(t--) solve(); exit(0); }