POJ 3087 Shuffle'm Up(模拟或者BFS)

矫情吗；* 2022-05-18 07:50 148阅读 0赞

[题目链接][Link 1]

题目大意：读入三个字符串s1，s2，s3，每次将s1和s2字符串依次交叉（s2开始），例如设s1：ABC ，s2：DEF 则第一次交叉后为DAEBFC，然后又取上面的一半作为s2，下面的一半作为s1，又开始依次交叉，问你经过多少次后，能变成s3的状态，每次输出两个数，第一个数字代表是第几组测试数据，第二个数字代表最少需要多少次，如果始终不能变成s3则输出-1。

分析：

解法1：如果当前组合成的字符串之前已经出现过了，说明又来到了之前的状态，那么之后会重复之前进行过的操作，即永远也无法变成s3，用一个map来对每次新组合成的字符串进行标记，然后模拟整个交换的过程即可。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include <iomanip>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 1e2+7;
    const double eps = 1e-8;
    int c;
    string s1,s2,s3;
    map<string,int>mp;
    
    int slove()
    {
        int cnt=0;
        mp.clear();
        while(true){
            cnt++;
            string ss="";
            for(int i=0;i<c;i++)
                ss=ss+s2[i]+s1[i];
            if(mp[ss])
                return -1;
            else if(ss==s3)
                return cnt;
            else{
                mp[ss]=1;
                s1="";
                for(int i=0;i<c;i++)
                    s1=s1+ss[i];
                s2="";
                for(int i=c;i<2*c;i++)
                    s2=s2+ss[i];
            }
        }
    }
    
    int main()
    {
        int T,kase=0;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&c);
            cin>>s1>>s2>>s3;
            cout<<++kase<<" "<<slove()<<endl;
        }
        return 0;
    }

解法2：因为是问最小操作次数，所以其实也可以用BFS来做，只不过每次只有一种状态转移而已，用一个map标记一下每次出现的状态，然后BFS进行每次的操作即可。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include <iomanip>
    #include<utility>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    const int maxn = 1e2+7;
    const double eps = 1e-8;
    int c;
    string s1,s2,s3;
    
    struct node{
        string ss;
        int cnt;
    }vs,now,next;
    
    int BFS()
    {
        queue<node>q;
        map<string,int>mp;
        while(!q.empty()) q.pop();
        mp.clear();
        vs.ss="";
        for(int i=0;i<c;i++)
            vs.ss=vs.ss+s2[i]+s1[i];
        vs.cnt=1;
        if(vs.ss==s3) return vs.cnt;
        q.push(vs);
        mp[vs.ss]=1;
        string temp;
        while(!q.empty()){
            now=q.front();
            q.pop();
            temp="";
            for(int i=0;i<c;i++)
                    temp=temp+now.ss[i+c]+now.ss[i];
            if(temp==s3)
                return now.cnt+1;
            else if(mp[temp])
                return -1;
            else{
                mp[temp]=1;
                next.ss=temp;
                next.cnt=now.cnt+1;
                q.push(next);
            }
        }
        return -1;
    }
    
    int main()
    {
        int T,kase=0;
        scanf("%d",&T);
        while(T--)
        {
            cin>>c;
            cin>>s1>>s2>>s3;
            cout<<++kase<<" "<<BFS()<<endl;
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3087