poj3087 Shuffle'm Up(bfs)

时间:2022-08-18 08:20:03

http://poj.org/problem?id=3087

注意复制字符串的时候,要在末尾加上'\0',否则导致strcmp出错。

还有就是开数组大小的时候看清楚一点,别开错了debug了好久。

 #include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
using namespace std;
int t, n, k, kase=;
char s12[], s1[], s2[];
char vis[][];
typedef struct{
int cnt;
char s[];
}Node;
int panduan(Node a)
{
if(!strcmp(s12, a.s))
return ;
return ;
}
int panduan2(Node a)
{
for(int i = ; i < k; i++){
if(!strcmp(a.s, vis[i])){
return ;
}
}
return ;
}
void bfs()
{
k=;
int flag=;
Node node;
queue<Node> q;
int j = ;
for(int i = ; i < *n; i += ){
node.s[i] = s2[j++];
}
j = ;
for(int i = ; i < *n; i += ){
node.s[i] = s1[j++];
}
node.s[*n] = '\0';
node.cnt=;
q.push(node);
while(!q.empty()){
Node t = q.front(), p;
strcpy(vis[k++], t.s);
q.pop();
/*for(int i = 0; i < 2*n; i++){
cout << t.s[i];
} cout << endl;*/
if(panduan(t)){
flag=;
cout << ++kase << " " << t.cnt << endl;
break;
}
//拆分
j=;
for(int i = ; i < n; i++){
s1[j++] = t.s[i];
}
j=;
for(int i = n; i < *n; i++){
s2[j++] = t.s[i];
}
//合并
j=;
for(int i = ; i < *n; i += ){
p.s[i] = s2[j++];
}
j = ;
for(int i = ; i < *n; i += ){
p.s[i] = s1[j++];
}
p.s[*n] = '\0';
p.cnt=t.cnt+;
if(panduan2(p)){
//strcpy(vis[k++], p.s);
q.push(p);
}
}
if(!flag){
cout << ++kase << " " << "-1" << endl;
}
}
int main()
{
cin >> t;
while(t--){
cin >> n;
cin >> s1 >> s2 >> s12;
memset(vis, , sizeof(vis));
//cout << ++kase << " ";
bfs();
}
return ;
}