POJ - 3087 - Shuffle'm Up(模拟)

题目链接

题意：

已知两堆牌s1和s2的初始状态， 其牌数均为c，按给定规则能将他们相互交叉组合成一堆牌s12，
再将s12的最底下的c块牌归为s1，最顶的c块牌归为s2，依此循环下去。
现在输入s1和s2的初始状态 以及 预想的最终状态s12

问s1 s2经过多少次洗牌之后，最终能达到状态s12，若永远不可能相同，则输出"-1"。

题解：

虽然归类于kuangbin搜索专题，但个人感觉模拟更好做，直接用map判重，进行模拟就可以。
如果出现了一个出现过的非目标串，则输出-1，因为此时操作是一个环无法到达目标串

AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;
const int maxn=120;
string s1,s2,s,s12;
int main(){
    int t,n,tt=1;
    cin>>t;
    while(tt<=t){
        cin>>n;
        cin>>s1>>s2>>s;
        map<string,bool>vis;
        vis[s]=1;

        int cnt=0;
        while(1){
            s12="";
            for(int i=0;i<n;i++){
                s12+=s2[i];
                s12+=s1[i];
            }
            s12+="\0";
            cnt++;

            if(s12==s){
                cout<<tt<<" "<<cnt<<endl;
                break;
            }
            if(vis[s12]){
                cout<<tt<<" "<<-1<<endl;
                break;
            }

            vis[s12]=1;
            s1="";
            s2="";
            for(int i=0;i<n;i++){
                s1+=s12[i];
                s2+=s12[i+n];
            }
            s1+="\0";
            s2+="\0";
        }
        tt++;

    }
    return 0;
}