#include #pragma GCC optimize ("Ofast") using namespace std; #define rep(i,a,b) for(ll i = a; i vl; typedef pair pll; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); ll n,m; cin>>n>>m; vector> a(n,vector(m)); vector> b(n,vector(m)); vector> obs(n,vector(m)); rep(i,0,n){ rep(j,0,m){ char c; cin>>c; a[i][j] = (c=='*'); obs[i][j] = (c=='X'); } } rep(i,0,n){ rep(j,0,m){ char c; cin>>c; b[i][j] = (c=='*'); } } auto bfs = [&](vector> &mask, vector> &start){ vector> dist(n,vector(m,-1)); vector> par(n,vector(m,{-2,-2})); vector ord; queue> q; rep(i,0,n) rep(j,0,m) if(start[i][j]) q.emplace(i,j,0,pll({-1,-1})); while(q.size()){ ll i,j,d; pll currPar; tie(i,j,d, currPar) = q.front(); q.pop(); if(i<0||j<0||i>=n||j>=m) continue; if(dist[i][j]!=-1) continue; if(obs[i][j]) continue; if(!mask[i][j]) continue; par[i][j] = currPar; dist[i][j] = d; ord.emplace_back(i,j); q.emplace(i-1,j,d+1,pll({i,j})); q.emplace(i+1,j,d+1,pll({i,j})); q.emplace(i,j+1,d+1,pll({i,j})); q.emplace(i,j-1,d+1,pll({i,j})); } return tuple, vector>, vector>> {ord,par,dist}; }; // Find a path vector> mask(n,vector(m,true)); vector ord; vector> parent; vector> dist; tie(ord,parent,dist) = bfs(mask,a); vector path; ll bestBDist = 1e18; rep(i,0,n) rep(j,0,m) if(b[i][j] && bestBDist>dist[i][j]) bestBDist = dist[i][j]; rep(i,0,n){ if(sz(path)) break; rep(j,0,m){ if(sz(path)) break; if(b[i][j] && dist[i][j] == bestBDist && parent[i][j].first!=-2){ if(parent[i][j].first==-1){ path.emplace_back(i,j); break; } else if(!b[parent[i][j].first][parent[i][j].second]){ do { path.emplace_back(i,j); tie(i,j) = parent[i][j]; } while (i!=-1); } } } } if(sz(path)==0){ cout<<"NO"<> start(n,vector(m,false)); start[path.back().first][path.back().second] = true; vector addOrder; tie(addOrder,parent,dist) = bfs(mask,start); reverse(all(addOrder)); // Find removeOrder mask = a; for(auto p: path){ mask[p.first][p.second] = true; } start.assign(n,vector(m,false)); start[path.front().first][path.front().second] = true; vector removeOrder; tie(removeOrder,parent,dist) = bfs(mask,start); // Calculate answer vector> ans; vector> dontRemove(n,vector(m,false)); vector> currentBlob(n,vector(m,false)); rep(i,0,n) rep(j,0,m) currentBlob[i][j] = a[i][j]; addOrder.pop_back(); while(true){ while(removeOrder.size() && dontRemove[removeOrder.back().first][removeOrder.back().second]){ removeOrder.pop_back(); } while(addOrder.size() && currentBlob[addOrder.back().first][addOrder.back().second]){ dontRemove[addOrder.back().first][addOrder.back().second] = true; addOrder.pop_back(); } if(sz(addOrder)){ assert(sz(removeOrder)); currentBlob[removeOrder.back().first][removeOrder.back().second] = false; currentBlob[addOrder.back().first][addOrder.back().second] = true; ans.emplace_back(removeOrder.back().first,removeOrder.back().second,addOrder.back().first,addOrder.back().second); removeOrder.pop_back(); addOrder.pop_back(); } else break; } cout<<"YES"<