#include #define pb push_back #define en return 0; using namespace std; typedef long long ll; typedef pair pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 55; const int dx[] = {0,0,1,-1}; const int dy[] = {1,-1,0,0}; char sak[N][N], beig[N][N]; int dist[N][N]; pair par[N][N]; int n, m; bool inside(int x, int y) { return (0 > q; q.push({stx,sty}); while(!q.empty()) { int x = q.front().fi, y = q.front().se; q.pop(); for(int d = 0;d<4;d++) { int nwx = x+dx[d], nwy = y+dy[d], nwd = dist[x][y]+1; if(inside(nwx,nwy)&&sak[nwx][nwy]!='X'&&dist[nwx][nwy]>nwd) { par[nwx][nwy]={x,y}; dist[nwx][nwy]=nwd; q.push({nwx,nwy}); } } } } pair furthest(int stx, int sty, bool insecond = 0) { for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) dist[i][j]=1e9; dist[stx][sty]=0; queue > q; q.push({stx,sty}); while(!q.empty()) { int x = q.front().fi, y = q.front().se; q.pop(); for(int d = 0;d<4;d++) { int nwx = x+dx[d], nwy = y+dy[d], nwd = dist[x][y]+1; if(inside(nwx,nwy)&&sak[nwx][nwy]=='*'&&dist[nwx][nwy]>nwd) { dist[nwx][nwy]=nwd; q.push({nwx,nwy}); } } } int ansx = -1, ansy = -1; for(int i = 1;i<=n;i++) { for(int j = 1;j<=m;j++) { if(dist[i][j]==1e9) continue; if(insecond&&beig[i][j]=='*') continue; if(ansx==-1||dist[i][j]>dist[ansx][ansy]) ansx=i, ansy=j; } } return {ansx,ansy}; } int main() { fastIO; cin >> n >> m; int sakx = -1, saky = -1, beigx = -1, beigy = -1; for(int i = 1;i<=n;i++) { for(int j = 1;j<=m;j++) { cin >> sak[i][j]; if(sak[i][j]=='*') sakx=i, saky=j; } } for(int i = 1;i<=n;i++) { for(int j = 1;j<=m;j++) { cin >> beig[i][j]; if(beig[i][j]=='*') beigx=i, beigy=j; } } bfs(sakx,saky); if(dist[beigx][beigy]==1e9) return cout << "NO", 0; cout << "YES\n"; int cx = beigx, cy = beigy; vector > pth; while(cx!=sakx||cy!=saky) { pth.pb({cx,cy}); pair prv = par[cx][cy]; cx = prv.fi; cy = prv.se; } reverse(pth.begin(),pth.end()); vector,pair > > ans; for(auto t:pth) { int x = t.fi, y = t.se; if(sak[x][y]=='*') continue; assert(sak[x][y]=='.'); auto t2 = furthest(x,y); swap(sak[t2.fi][t2.se],sak[x][y]); ans.pb({t2,{x,y}}); } /* for(auto x:ans) cout << x.fi.fi << " " << x.fi.se << " : " << x.se.fi << " " << x.se.se << endl; for(int i = 1;i<=n;i++) { for(int j = 1;j<=m;j++) cout << sak[i][j]; cout << endl; } */ while(1) { auto from = furthest(beigx,beigy,1); sak[from.fi][from.se]='.'; //cout << from.fi << " " << from.se;en if(from.fi==-1) break; pair to = {-1,-1}; for(int i = 1;i<=n;i++) { for(int j = 1;j<=m;j++) { for(int d = 0;d<4;d++) { int nwx = i+dx[d], nwy = j+dy[d]; if(!inside(nwx,nwy)) continue; if(sak[i][j]=='*'&&sak[nwx][nwy]=='.'&&beig[nwx][nwy]=='*') { if(to.fi==-1||dist[to.fi][to.se]>dist[i][j]) to={nwx,nwy}; } } } } ans.pb({from,to}); swap(sak[from.fi][from.se],sak[to.fi][to.se]); } cout << ans.size() << "\n"; for(auto x:ans) cout << x.fi.fi << " " << x.fi.se << " " << x.se.fi << " " << x.se.se << "\n"; return 0; }