<untitled> (C++)

Ревизии: current

text/plain
text/html
source
Old rev.:
#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

string code(string pat, vector<char> key){
    string res = pat;

    for (int i = 0; i < (int)key.size(); i++)
        res[i] = pat[key[i]];

    return res;
}

int n, p, l, t, ans = -1;
vector<vector<char> > keys;
string cur, pre;
map<string, int> save;

void meet(string s, int k){
    if (save[s] == 0 || save[s] > k)
        save[s] = k;

    if (k > t)
        return;
   
    for (int i = 0; i < p; i++)
        meet(code(s, keys[i]), k + 1);
}

void midle(string s, int k){
    if (save[s] != 0)
        ans == -1 ? ans = k + save[s]: ans = min(ans, k + save[s]);

    if (s == pre)
        ans == -1 ? ans = k : ans = min(ans , k);

    if (k > t)
        return;

    for (int i = 0; i < p; i++)
        midle(code(s, keys[i]), k + 1);
}

int main(){
    cin >> n >> p >> l;

    t = (l + 1) / 2;

    keys.resize(p, vector<char>(n, 0));
   
    cin >> pre >> cur;

    if (pre == cur){
        cout << 0 << endl;

        return 0;
    }

    for (int i = 0; i < p; i++){
        string q;

        cin >> q;

        for (int j = 0; j < n; j++)
            keys[i][j] = q[j] - 'a';
    }

    meet(pre, 0);

    midle(cur, 0);

    cout << ans << endl;

//  system("pause");

    return 0;
}
 

Комментарии:

Нет