<untitled> (C++)

Ревизии: current

text/plain
text/html
source
Old rev.:
#include <iostream>
#include <cstdio>
#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;
}

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

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

    return res;
}

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

void meet(){
    if (save.find(s) == save.end())
        save[s] = k;
    else
        save[s] = min(save[s], k);

    if (s == cur && k <= l)
        if (ans == -1)
            ans = k;
        else
            if (ans > k)
                ans = k;

    if (k > t)
        return;
   
    for (int i = 0; i < p; i++){
        k++;
        string e = s;

        s = code(s, keys[i]);

        meet();

        s = e;
        k--;
    }
}

void midle(){
    if (save.find(s) != save.end() && save[s] != 0 && k + save[s] <= l)
        ans == -1 ? ans = k + save[s]: ans = min(ans, k + save[s]);

    if (s == pre && k <= l)
        if (ans == -1)
            ans = k;
        else
            if (ans > k)
                ans = k;

    if (k > t)
        return;

    for (int i = 0; i < p; i++){
        string e = s;
        s = decode(s, keys[i]);
        k++;

        midle();

        k--;
        s = e;
    }
}

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

    k = 0;

    s = pre;

    meet();

    t++;

    k = 0;

    s = cur;

    midle();

    cout << ans << endl;

//  system("pause");

    return 0;
}
 

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

Нет