<untitled> (C++)

Ревизии: current

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

using namespace std;

int p, l, len, ans = 100, lim;
string s, f, t;
vector<string> keys(10);
map<string, int> m;
stack<string> str;

void rec(int k)
{
    s = str.top();
    if (k > lim)
    {
        str.pop();
        return;
    }
    if (m.find(s) == m.end())
        m[s] = k;
    else
        m[s] = min(m[s], k);
    for (int i = 0; i < p; i++)
    {
        for (int j = 0; j < len; j++)
            t[j] = s[keys[i][j]];
        str.push(t);
        rec(k+1);
        s = str.top();
    }
    str.pop();
}

void rec2(int k)
{
    s = str.top();
    if (k > lim)
    {
        str.pop();
        return;
    }
    if (m.find(s) != m.end())
        ans = k + m[s] < ans ? k + m[s] : ans;
    for (int i = 0; i < p; i++)
    {
        for (int j = 0; j < len; j++)
            t[j] = s[keys[i][j]];
        str.push(t);
        rec2(k+1);
        s = str.top();
    }
    str.pop();
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    cin >> len >> p >> l >> s >> f;
    t = s;
    for (int i = 0; i < p; i++)
    {
        cin >> keys[i];
        for (int j = 0; j < len; j++)
            keys[i][j] -= 'a';
    }
    lim = (l+1)/2;
    str.push(s);
    rec(0);
    lim = (l+1)/2+1;
    str.push(f);
    rec2(0);
    if (ans <= l)
        cout << ans;
    else
        cout << -1;
    return 0;
}

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

Нет