<untitled> (C++)

Ревизии: current

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

using namespace std;

int n, p, l, len, ans = 100, lim;
string s, f, keys[10], t;
map<string, int> m;

void rec(string s, int k)
{
    if (k > lim)
        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]];
        rec(t, k+1);
    }
}

void rec2(string s, int k)
{
    if (k > lim)
        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]];
        rec2(t, k+1);
    }
}

int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    cin >> n >> p >> l >> s >> f;
    t = s;
    len = s.length();
    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;
    rec(s, 0);
    lim = l/2+1;
    rec2(f, 0);
    if (ans <= l)
        cout << ans;
    else
        cout << -1;
    return 0;
}

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

Нет