欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

poj3087 Shuffle'm Up

程序员文章站 2022-03-23 11:08:24
...

题目链接:http://poj.org/problem?id=3087
题意:给你两塔牌,问你能否把这两塔牌,按照一定的步骤合并成目标的那一堆牌,看题目的图示就大概知道是什么样的操作了,就是两个字符串交叉叠在一起,如果不行,在从中间对半分成两个,再重新组合,如果能就输出操作步数,否则输出-1
解析:直接模拟就好了,每次组合起来的东西,标记一下,如果组合出来的已经标记了,说明一定不能组成了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
int main(void)
{
    string s1,s2,s12;
    int t,case_t = 1;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        cin>>s1>>s2>>s12;
        map<string,int>maple;
        int ans = 0;
        for(;;)
        {
            string tmp;
            for(int i=0;i<n;i++)
            {
                tmp.push_back(s2[i]);
                tmp.push_back(s1[i]);
            }
            ans++;
            if(tmp==s12)
            {
                printf("%d %d\n",case_t++,ans);
                break;
            }
            else if(maple[tmp])
            {
                printf("%d %d\n",case_t++,-1);
                break;
            }
            maple[tmp] = 1;
            s1 = tmp.substr(0,n);
            s2 = tmp.substr(n,n);
        }
    }
    return 0;
}