#include using namespace std; typedef long long ll; typedef long double ld; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; #define x first #define y second #define pb push_back #define eb emplace_back #define rep(i,a,b) for(auto i = (a); i < (b); ++i) #define REP(i,n) rep(i,0,n) #define all(v) begin(v), end(v) #define sz(v) ((int) (v).size()) #define rs resize vector>> figuren; vector> afstand; ll ox, oy; ll r,c; vector, pair>> stappen; void doeStap(ll xs, ll ys, ll xe ,ll ye){ stappen.push_back(make_pair(make_pair(xs,ys), make_pair(xe,ye))); figuren[0][xs][ys] = false; figuren[0][xe][ye] = true; } void zoekPad(ll xs, ll ys, ll t1, ll t2){ for(ll x=0;x> rij; rij.emplace(make_pair(xs,ys)); pair paar; ll nux,nuy; while(rij.size() > 0){ paar = rij.front(); rij.pop(); nux = paar.first; nuy = paar.second; for(ll dx = -1; dx<=1;dx++){ for(ll dy = -1; dy<=1;dy++){ if(abs(dx)+ abs(dy) == 1 && nux+dx >=0 && nux+dx < r && nuy+dy>=0 && nuy+dy afstand[nux][nuy] + 1){ afstand[nux+dx][nuy+dy] = afstand[nux][nuy]+1; rij.emplace(make_pair(nux + dx,nuy + dy)); } } } } } void zoekPad(ll xs, ll ys, ll t){ zoekPad(xs,ys,t,t); } bool bepaalOverlap(){ //Kijk of het simpel kan bool klopt = false; for(ll x = 0; x< r && !klopt;x++){ for(ll y = 0; y< c;y++){ if(figuren[0][x][y] && figuren[1][x][y]){ ox = x; oy = y; klopt = true; break; } } } if(klopt){ return true; } //Ga een pad maken ll xs=-1,ys =-1,xe = -1, ye =-1; for(ll x=0;x 1000000){ return false; } vector> pad; pad.push_back(make_pair(xe,ye)); ll nux = xe,nuy = ye; bool gezet; while(nux != xs || nuy !=ys){ gezet = false; for(ll dx = -1; dx <= 1 && !gezet; dx++){ for(ll dy = -1; dy<=1;dy++){ if(abs(dx) + abs(dy) == 1 && nux + dx >= 0 && nux + dx < r && nuy + dy >= 0 && nuy+dy < c && afstand[nux][nuy] == afstand[nux+dx][nuy+dy] + 1){ nux += dx; nuy += dy; pad.push_back(make_pair(nux,nuy)); gezet = true; break; } } } } //Kijk waar we willen beginnen en eindigen ll astart; for(ll a = 0; a= 0;a--){ nux = pad[a].first; nuy = pad[a].second; if(figuren[1][nux][nuy]){ xe = nux; ye = nuy; aeind = a; break; } } //Ga lopen zoekPad(xs,ys,0); vector>> vakjes; for(ll x=0;x= aeind; a--){ i = vakjes.size() - (astart - a); doeStap(vakjes[i].second.first, vakjes[i].second.second, pad[a].first, pad[a].second); } ox = xe; oy = ye; } void vulOp(){ //Bepaal wat er gaat lopen zoekPad(ox,oy,0); vector>> vakjesbegin; for(ll x=0;x= 0; i--){ sx = vakjesbegin[i].second.first; sy = vakjesbegin[i].second.second; ex = -1; ey = -1; for(ll x = 0; x < r;x++){ for(ll y = 0; y < c;y++){ voldoet = figuren[1][x][y] && ((x == sx && y == sy) || (!figuren[0][x][y])); if(voldoet && (ex == -1 || afstand[x][y] < afstand[ex][ey])){ ex = x; ey = y; } } } if(ex != sx || ey != sy){ doeStap(sx,sy,ex,ey); } } } signed main(){ cin>>r; cin>>c; string s; vector> open; for(ll t=0;t<2;t++){ vector> vec; for(ll x = 0; x< r;x++){ cin >> s; vector vec2; vector vecopen; for(ll y = 0; y< c;y++){ vec2.push_back(s[y] == '*'); vecopen.push_back(s[y] != 'X'); } vec.push_back(vec2); if(t == 0){ open.push_back(vecopen); } } figuren.push_back(vec); } figuren.push_back(open); for(ll x=0;x vec; for(ll y = 0; y< c;y++){ vec.push_back(-1); } afstand.push_back(vec); } //Kijk of het kan if(!bepaalOverlap()){ cout << "NO" <