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;
}