Untitled
// zad 5 // Ustalmy, ze rozumiemy odleglosc miedzy dwoma slowami jako liczbe liter, // ktorymi sie roznia (czyli d(kot, dom) = 4) // Nie mozemy sie przeiterowac przez wszystkie pary (bo jest ich za duzo) // dlatego iterujemy sie przez k par // sprawdzamy czy znalezlismy wystarczajaca liczbe par miedzy ktorymi istnieje metamorfoza // jezeli nie to dodajemy kolejne k, jezeli tak to konczymy #include<bits/stdc++.h> using namespace std; vector<string> wczytaj(int dlugosc) { ifstream file("pliki/slownik.txt"); vector<string> slownik; string line; while (getline(file, line)) { if (line.length() == dlugosc) { slownik.push_back(line); } } file.close(); return slownik; } int main() { int n, m; cin >> n >> m; const int partie_szukanych_par = 10; const int partie_szukanych_potencjalnych_posrednikow = 10; vector<string> slownik = wczytaj(n); cout << slownik.size() << endl; // roznia sie wszystkimi literami, maja ich tyle samo. vector<pair<int, int>> dobre_pary; vector<unordered_set<int>> litery_w_slowach = {}; for (int i = 0; i < slownik.size(); i++) { unordered_set<int> litery = {}; for (int j = 0; j < n; j++) { litery.insert(slownik[i][j]); } litery_w_slowach.push_back(litery); } vector<vector<string>> metamorfozy = {}; int i_start = 0; while(metamorfozy.size() < m) { for (int i = i_start; i < slownik.size(); i++) { for (int j = i + 1; j < slownik.size(); j++) { if (slownik[i].length() != slownik[j].length()) { continue; } if (litery_w_slowach[i].size() != n && litery_w_slowach[j].size() != n) { continue; } bool wspolne_litery = false; for (int k = 0; k < n; k++) { // przeszukujemy unordered_set dla slowa i w czasie O(1) dla kazdej litery w slowie j if (litery_w_slowach[i].find(slownik[j][k]) != litery_w_slowach[i].end()) { wspolne_litery = true; break; } } if (!wspolne_litery) { dobre_pary.push_back({i, j}); } } if (dobre_pary.size() >= partie_szukanych_par) { i_start = i + 1; break; } } // szukamy pary miedzy ktorymi potencjalnie istnieje metamorfoza for (auto para : dobre_pary) { bool metamorfoza_znaleziona = false; // mozna z nich skorzystac przy metamorfozie (słów s_posrednik) // musi być, że d(s_posrednik, s1) <= n/2 i d(s_posrednik, s2) = n/2 // gdzie s1, s2 to słowa z pary int j_start = 0; vector<vector<int>> potencjalni_posrednicy = {}; // {indeks_posrednika, d1, d2} vector<vector<int>> nowe_potencjalni_posrednicy = {}; do { // nowa partia potencjalnych posrednikow nowe_potencjalni_posrednicy = {}; for (int j = j_start; j < slownik.size(); j++) { if (j == para.first || j == para.second) { continue; } int d1 = 0; int d2 = 0; for (int k = 0; k < n; k++) { if (litery_w_slowach[j].find(slownik[para.first][k]) != litery_w_slowach[j].end()) { d1++; } if (litery_w_slowach[j].find(slownik[para.second][k]) != litery_w_slowach[j].end()) { d2++; } } if (d1 + d2 == n) { nowe_potencjalni_posrednicy.push_back({j, d1, d2}); if (nowe_potencjalni_posrednicy.size() == partie_szukanych_potencjalnych_posrednikow) { cout << "found" << endl; j_start = j + 1; break; } } } for (auto nowy : nowe_potencjalni_posrednicy) { potencjalni_posrednicy.push_back(nowy); } // DFS stack<int> stos; int aktualny = para.first; int aktualny_dystans = 0; stos.push(aktualny); while(!stos.empty()) { stos.pop(); if (aktualny == para.second) { metamorfoza_znaleziona = true; break; } for (auto posrednik : potencjalni_posrednicy) { int potencjalny = posrednik[0]; int d1 = posrednik[1]; int d2 = posrednik[2]; bool istnieje_krawedz = true; for (int k = 0; k < n; k++) { if ( litery_w_slowach[aktualny].find(slownik[potencjalny][k]) != litery_w_slowach[aktualny].end() ) { istnieje_krawedz = false; break; } if ( slownik[aktualny][k] == slownik[potencjalny][k] ) { istnieje_krawedz = false; break; } } if (istnieje_krawedz) { stos.push(potencjalny); aktualny_dystans = d1; } } } // cout << "Analizowanie metamorfozy . . . | Partia potencjalnych posrednikow: " << j_start << " Nowe " << nowe_potencjalni_posrednicy.size() << endl; } while ((j_start < slownik.size() && !metamorfoza_znaleziona) && nowe_potencjalni_posrednicy.size() == partie_szukanych_potencjalnych_posrednikow); } } return 0; }
Leave a Comment