#include using namespace std; #define ll long long #define pb push_back const int N=55; char S[N][N],E[N][N],tmp[N][N],cellCnt; vector> ans; int dist[N][N],n,m,mv[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; bool In(int x,int y){ return x>=1 && x<=n && y>=1 && y<=m; } bool Check(char grid[N][N], int x,int y,int type){ if(type==0){ return grid[x][y]=='*'; }else if(type==1){ return S[x][y]=='*' && grid[x][y]=='*'; } } void BFS(char grid[N][N],int x,int y,int type=0){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dist[i][j]=-1; } } queue q; q.push(x*N+y); dist[x][y]=0; while(q.size()){ int x=q.front()/N; int y=q.front()%N; q.pop(); for(int i=0;i<4;i++){ int nx=x+mv[i][0]; int ny=y+mv[i][1]; if(In(nx,ny) && dist[nx][ny]==-1){ if(Check(grid,nx,ny,type)){ dist[nx][ny]=dist[x][y]+1; q.push(nx*N+ny); } } } } } void BFS2(){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dist[i][j]=-1; } } queue q; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(E[i][j]=='*'){ dist[i][j]=0; q.push(i*N+j); } } } while(q.size()){ int x=q.front()/N; int y=q.front()%N; q.pop(); for(int i=0;i<4;i++){ int nx=x+mv[i][0]; int ny=y+mv[i][1]; if(In(nx,ny) && dist[nx][ny]==-1){ if(E[nx][ny]!='X'){ dist[nx][ny]=dist[x][y]+1; q.push(nx*N+ny); } } } } } int dfsNow; void BuildDFS(int x,int y){ if(dfsNow>=cellCnt)return; dfsNow++; tmp[x][y]='*'; int target=dist[x][y]==0?0:dist[x][y]-1; for(int i=0;i<4;i++){ int nx=x+mv[i][0]; int ny=y+mv[i][1]; if(In(nx,ny) && tmp[nx][ny]=='.' && dist[nx][ny]==target){ BuildDFS(nx,ny); if(target!=0)break; } } } void BuildTmp(int x,int y){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ tmp[i][j]=S[i][j]=='X'?'X':'.'; } } dfsNow=0; BuildDFS(x,y); } void Print(char grid[N][N]){ for(int i=1;i<=n;i++)printf("%s\n",grid[i]+1); } /*bool was[N][N]; void DFS(int x,int y,int bx,int by){ if(was[x][y])return; was[x][y]=true; for(int i=0;i<4;i++){ int nx=x+mv[i][0]; int ny=y+mv[i][1]; if(In(nx,ny) && S[nx][ny]=='*' && (nx!=bx || ny!=by)){ DFS(nx,ny,bx,by); } } } bool Bridge(int x,int y){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ was[i][j]=false; } } int cnt=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(!was[i][j] && S[i][j]=='*' && (i!=x || j!=y)){ DFS(i,j,x,y); cnt++; } } } return cnt>1; }*/ bool bridge[N][N]; int disc[N][N],low[N][N],tid; void Tarjan(int x,int y,bool root=true){ disc[x][y]=low[x][y]=++tid; int chCnt=0; for(int i=0;i<4;i++){ int nx=x+mv[i][0]; int ny=y+mv[i][1]; if(In(nx,ny) && S[nx][ny]=='*'){ if(!disc[nx][ny]){ Tarjan(nx,ny,false); chCnt++; if(low[nx][ny]>=disc[x][y]){ bridge[x][y]=true; } low[x][y]=min(low[x][y],low[nx][ny]); }else{ low[x][y]=min(low[x][y],disc[nx][ny]); } } } if(root && chCnt>1)bridge[x][y]=true; } void FindBridges(){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ bridge[i][j]=false; disc[i][j]=0; low[i][j]=0; } } tid=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(S[i][j]=='*' && !disc[i][j]){ Tarjan(i,j,true); } } } } void Work(int x,int y){ while(1){ BFS(tmp,x,y,1); int bx=-1,by=-1,ex=-1,ey=-1; FindBridges(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(dist[i][j]==-1 && S[i][j]=='*'){ if(!bridge[i][j]){ bx=i; by=j; } } if(dist[i][j]==-1 && tmp[i][j]=='*'){ for(int k=0;k<4;k++){ int nx=i+mv[k][0]; int ny=j+mv[k][1]; if(In(nx,ny) && dist[nx][ny]!=-1){ ex=i; ey=j; } } } } } if(bx==-1 || ex==-1)break; S[bx][by]='.'; S[ex][ey]='*'; ans.pb({bx,by,ex,ey}); } } void No(){ printf("NO\n"); exit(0); } int main(){ scanf("%i %i",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",S[i]+1); } for(int i=1;i<=n;i++){ scanf("%s",E[i]+1); } cellCnt=0; for(int i=1;i<=n;i++){ //printf("%i\n",cellCnt); for(int j=1;j<=m;j++){ if(S[i][j]=='*')cellCnt++; } } while(true){ int ex,ey; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(E[i][j]=='*'){ ex=i; ey=j; } } } //printf("EEE\n"); BFS(E,ex,ey); int sx=-1,sy=-1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(S[i][j]=='*'){ if(dist[i][j]!=-1){ sx=i; sy=j; } } } } if(sx!=-1){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ tmp[i][j]=E[i][j]; } } Work(sx,sy); break; }else{ //printf(":D\n"); BFS2(); int mn=-1; int sx,sy; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(dist[i][j]==-1 && S[i][j]=='*'){ No(); } if(S[i][j]=='*'){ if(mn==-1 || mn>dist[i][j]){ mn=dist[i][j]; sx=i; sy=j; } } } } BuildTmp(sx,sy); //Print(tmp); Work(sx,sy); } } printf("YES\n"); printf("%i\n",ans.size()); for(auto p:ans)printf("%i %i %i %i\n",p[0],p[1],p[2],p[3]); return 0; }