POJ.3087 Shuffle’m Up （模拟）

题意分析

给定两个长度为len的字符串s1和s2， 接着给出一个长度为len*2的字符串s12。

将字符串s1和s2通过一定的变换变成s12，找到变换次数

变换规则如下：

假设s1=12345,s2=67890

变换后的序列 s=6172839405

如果s和s12完全相等那么输出变换次数

如果不完全相等，s的前半部分作为s1，后半部分作为s2，重复上述过程。

直接模拟，注意给出的顺序是从底到上的。

代码总览

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <set>

#define nmax 205

using namespace std;

char str1[nmax],str2[nmax],str[nmax];

int t,ans,n;

void change(char temp[])

{

    int pos = 0;

    for(int i = 0;i<n;++i){

        temp[pos++] = str2[i];

        temp[pos++] = str1[i];

    }

    temp[2*n] = '\0';

    ans++;

}

void split(char temp[])

{

    int i;

    for(i = 0;i<n;++i)

        str1[i] = temp[i];

    str1[i] = '\0';

    for(int j = 0;j<n;++j,++i)

        str2[j] = temp[i];

    str2[i] = '\0';

}

void bfs()

{

    char temp[nmax];

    memset(temp,0,sizeof(temp));

    change(temp);

    set<string> s;

    s.clear();

    while(1){

        if(strcmp(temp,str) == 0) return;

        if(s.count(temp) == 1){

            ans = -1;

            return;

        }else{

            s.insert(temp);

        }

        split(temp);

        change(temp);

    }

}

int main()

{

    scanf("%d",&t);

    for(int i = 1; i<=t;++i){

        ans = 0;

        scanf("%d",&n);

        scanf("%s",str1);

        scanf("%s",str2);

        scanf("%s",str);

        bfs();

        printf("%d %d\n",i,ans);

    }

    return 0;

}