比赛 |
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;
}