<untitled> (C++)

Ревизии: current

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

using namespace std;

#define maxN 300000

string code(string pat, string key){
    string res = pat;

    for (int i = 0; i < (int)key.length(); i++)
        res[i] = pat[key[i] - 'a'];

    return res;
}

map<string, bool> check;

int main(){
    int n, p, l;

    cin >> n >> p >> l;

    string prev;
    string cur;

    vector<string> key;

    key.resize(p);

    cin >> prev >> cur;

    for (int i = 0; i < p; i++)
        cin >> key[i];

    vector<string> q(maxN);
    vector<int> cnt(maxN);
    int h = 0, t = 0;

    q[t] = prev;
    cnt[t++] = 0;

    for (; h != t;){
        string tmp = q[h];
        int len = cnt[h];

        h = (h + 1) % maxN;

        if (len > l)
            break;

        if (tmp == cur){
            cout << len << endl;

//          system("pause");

            return 0;
        }

        for (int i = 0; i < p; i++){
            q[t] = code(tmp, key[i]);

            if (!check[q[t]]){
                cnt[t] = len + 1;

                check[q[t]] = true;

                t = (t + 1) % maxN;
            }
        }
    }

    cout << "-1" << endl;

//  system("pause");

    return 0;
}
 

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

Нет