#include #define int long long using namespace std; string to_string(string s) { return s; } template string to_string(T v) { string res = "["; for (const auto &x : v) { res += to_string(x) + ", "; } res += "]"; return res; } void dbg_out() { cout << endl; } template void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif using ll = long long; using vi = vector; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) const int MAXN = 51; int nbLignes, nbColonnes; char init[MAXN][MAXN]; char final[MAXN][MAXN]; bool claimed[MAXN][MAXN]; struct Pos { int x,y; }; Pos origine; Pos D[4] = {{-1,0},{0,-1},{0,1},{1,0}}; bool dedans(Pos pos) { return pos.x >= 0 && pos.y >=0 && pos.x < nbLignes && pos.y < nbColonnes; } Pos trouveCommun() { for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes;j ++) { if (final[i][j] == '*' && init[i][j] == '*') return {i,j}; } } return {-1,-1}; } void marqueClaim(Pos orig) { queue Q; Q.push(orig); for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) claimed[i][j] = false; } while (!Q.empty()) { auto actu = Q.front(); Q.pop(); if (claimed[actu.x][actu.y]) continue; claimed[actu.x][actu.y] = true; for (auto delta : D) { Pos npos = {delta.x + actu.x, delta.y + actu.y}; if (dedans(npos) && !claimed[npos.x][npos.y] && final[npos.x][npos.y] == '*' && init[npos.x][npos.y] == '*') Q.push(npos); } } } bool vu[MAXN][MAXN]; void initVu() { for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) { vu[i][j] = false; } } } vector ordre; void constructArbre(Pos orig) { vu[orig.x][orig.y] = true; for (auto delta : D) { Pos npos = {delta.x + orig.x , orig.y + delta.y}; if (dedans(npos) && !vu[npos.x][npos.y] && init[npos.x][npos.y] == '*' && !claimed[npos.x][npos.y]) { constructArbre(npos); } } ordre.push_back(orig); } vector > sol; void manger() { vector disponible; for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) { if (claimed[i][j]) { for (auto delta : D) { Pos npos = {delta.x + i , delta.y + j}; if (dedans(npos) && final[npos.x][npos.y] == '*' && !claimed[npos.x][npos.y]) { disponible.push_back(npos); } } } } } dbg(disponible.size() , ordre.size()); while (!ordre.empty() && !disponible.empty()) { Pos actu = disponible.back(); disponible.pop_back(); if (!claimed[actu.x][actu.y]) { Pos autre = ordre.back(); sol.push_back({ordre.back() , actu}); ordre.pop_back(); claimed[actu.x][actu.y] = true; init[autre.x][autre.y] = '.'; init[actu.x][actu.y] = '*'; for (auto delta : D) { Pos npos = {delta.x + actu.x , delta.y + actu.y}; if (dedans(npos) && final[npos.x][npos.y] == '*' && !claimed[npos.x][npos.y] && init[npos.x][npos.y] == '.') { disponible.push_back(npos); } } } } //fini de manger } int taille = 0; bool fini () { int cnt = 0; for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) { cnt += claimed[i][j]; } } return (cnt == taille); } void iteration() { initVu(); ordre.clear(); dbg(origine.x,origine.y); marqueClaim(origine); bool trouve = false; /* for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) { cout< Q; Q.push(orig); while (!Q.empty()) { auto actu = Q.front(); Q.pop(); if (init[actu.x][actu.y] == '*') return true; if (vu[actu.x][actu.y]) continue; vu[actu.x][actu.y] = true; for (auto delta : D) { Pos npos = {actu.x + delta.x, actu.y + delta.y}; if (dedans(npos) && init[npos.x][npos.y] != 'X') Q.push(npos); } } return false; } vector chemin; vector vraiChemin; void trouve(Pos actu) { if (vraiChemin.size() > 0) return; if (init[actu.x][actu.y] == '*') { for (auto el : chemin) { vraiChemin.push_back(el); } vraiChemin.push_back(actu); return; } if (vu[actu.x][actu.y]) return; vu[actu.x][actu.y] = true; chemin.push_back(actu); for (auto delta : D) { Pos npos = {actu.x + delta.x , actu.y + delta.y}; if (dedans(npos) && init[npos.x][npos.y] != 'X') trouve(npos); } chemin.pop_back(); } void premiereIteration() { origine = trouveCommun(); if (origine.x != -1) return; for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) { if (final[i][j] == '*') { origine = {i,j}; break; } } if (origine.x != -1) break; } if (!accessible(origine)) { cout<<"NO"<> nbLignes >> nbColonnes; for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) { cin >> init[i][j]; if (init[i][j] == '*') taille++; } } for (int i = 0 ; i < nbLignes ; i++) { for (int j = 0 ; j < nbColonnes ; j++) { cin >> final[i][j]; } } premiereIteration(); dbg("AA"s); while (!fini()) { iteration(); // dbg("B"s); } // iteration(); cout<<"YES"<