比赛 20120703 评测结果 AAATTTTTTT
题目名称 基因重组 最终得分 30
用户昵称 王者自由 运行时间 8.306 s
代码语言 C++ 内存使用 3.16 MiB
提交时间 2012-07-03 09:16:52
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
const int N = 20;
int n, m;
char s1[N], t1[N];
string t;
void BFS(string s, int d, bool e) {
    if(s == t || d >= m) {
        m = min(m, d);
        return;
    }
    //fprintf(stderr, "%s %d %d\n", s.c_str(), d, e);
    string b(s, 1, n-1);
    b += s[0];
    BFS(b, d+1, 0);
    if(!e) {
        string a(s);
        swap(a[0], a[1]);
        BFS(a, d+1, 1);
    }
}
int main() {
    freopen("genea.in", "r", stdin);
    freopen("genea.out", "w", stdout);
    scanf("%d\n", &n);
    scanf("%s\n", s1);
    scanf("%s\n", t1);
    string s(s1);
    t = t1;
    m = n * n / 2;
    BFS(s, 0, 0);
    printf("%d\n", m);
    return 0;
}