【搜索】Shuffle'm Up

运用第i个s12和第i+1个s12中，每个位置具有的确定的映射关系:

pos = pos * 2 + 1 (pos < c)

pos = pos * 2 - c * 2 (pos >= c)

例如c =3， 则位置为 0 1 2 3 4 5  会映射成 3 0 4 1 5 2

从第1到第2c个位置依次进行匹配，用搜索应该也可以做，合适于数据大的情况。

#include<string.h>

#include<stdio.h>

int main(){

    int n, c;

    char s1[], s2[], s12[], des[];

    scanf("%d",&n);

    //cin >> n;

    for(int t = ; t <= n; t ++){

        scanf("%d %c %c %c",c,s1,s2,des);

        int ans = ;

        bool flag = false;

        char str1[];

        strcpy(str1, s1);  // str1保存原始状态的s1。

        while(!flag){

            int i, k = ;

            for(i = ; i < c; i ++){   // s1和s2按规则合成s12。

                s12[k ++] = s2[i];

                s12[k ++] = s1[i];

            }

            s12[k] = ;

            ans ++;

            if(!strcmp(s12, des)){   // 若s12与目标相同。

                flag = true;

                break;

            }

            for(i = , k = ; k < c; k ++)  // 新的s1。

                s1[i ++] = s12[k];

            s1[i] = ;

            for(i = , k = c; k <  * c; k ++)  // 新的s2。

                s2[i ++] = s12[k];

            s2[i] = ;

            if(!strcmp(s1, str1))  // 等到s1经过x次变换后回到str1，则说明不可能到达目标情况了。

                break;

        }

        if(flag) printf("%d %d\n",t,ans);

        else printf("%d -1",t);

    }

    return ;

}