POJ 3087 Shuffle'm Up(BFS +模拟)

阳光穿透心脏的1/2处 2024-02-17 19:07 50阅读 0赞

题意：给定长度都为C两个字符串，S1，S2，和一个要求的结果字符串S12。先把 S2 的最下面一张牌放在最下面，然后S1，S2交错的叠放，得到新的S12，再把S12最下面的C个字符赋值给S1，把剩下的赋值给S2，再次重复上面的过程。最后求出要得到目标字符串S，问最少需要几步。

#include<iostream>
    #include<queue>
    #include<map>
    #include<cstring>
    #include<string>
    using namespace std;
    string s1,s2,s12;
    int C;
    int count1;
    string yeild1(string &s1,string &s2){
    	    string temp;
    	    int i;
    		for(i=0;i<2*C;i++){
    			if(i%2==0)temp+=s2[i/2];
    			else temp+=s1[i/2];
    		}
    			return temp;
    }
    void bfs(){
    	map<string,int>map1;
    	queue<string>q;
    	string temp=yeild1(s1,s2);
    	map1[temp]++;
    	q.push(temp);
    
    	while(!q.empty()){
    		string u=q.front();
    		q.pop();
            if(u==s12){
            	cout<<++count1<<" "<<map1[u]<<endl;
            	return ;
    		}
    		
    		s1=u.substr(0,C);           //分解子串，参数一；起始位置，参数二：个数（可省略） 
    		s2=u.substr(C);
    		string v=yeild1(s1,s2);
    		if(!map1.count(v)){
    			q.push(v);
    			map1[v]=map1[u]+1;
    		} 
    	}
    	cout<<++count1<<" "<<-1<<endl;
    }
    int main(){
    	int N;
    	cin>>N;
    	count1=0;
    	while(N--){
    		cin>>C;
    		cin>>s1>>s2>>s12;
    		bfs();
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，50人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3087 Shuffle'm Up(BFS +模拟)

题意：给定长度都为C两个字符串，S1，S2，和一个要求的结果字符串S12。先把 S2 的最下面一张牌放在最下面，然后S1，S2交错的叠放，得到新的S12，再把S12最下面的C个

阳光穿透心脏的1/2处/ 2024年02月17日 19:07/ 0 赞/ 51 阅读

相关 Poj 3087 + Hdu 1312 + Hdu 1241 + Poj 3278 (基础BFS DFS)

DFS的剪枝真的很重要，还需要多加练习！ Poj 3087 Shuffle'm Up 其实是一道模拟题，被别人分类到了搜索里…… 题意：给你两堆纸牌，让你通过数次洗

布满荆棘的人生/ 2022年09月20日 15:01/ 0 赞/ 162 阅读

相关 POJ - 1835 - 模拟

题目链接：[POJ-1835][] 题目大意：宇航员在太空中行走，给定一个三维坐标系（x,y,z轴的正方向标号分别为0,1,2，负方向标号分别为3,4,5），他的起始位置

谁践踏了优雅/ 2022年07月17日 04:51/ 0 赞/ 165 阅读

相关 POJ4001-模拟象棋

Xiangqi <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

红太狼/ 2022年07月11日 07:20/ 0 赞/ 228 阅读

相关 N - Shuffle'm Up POJ - 3087——模拟

Think: 1洗牌，从st1和st2的底部开始，每次将st1放在st2上面，如果合并后与st相同，记录当前次数，然后结束，如果合并后不相同，取新的st下半部作为新的st1

「爱情、让人受尽委屈。」/ 2022年06月15日 02:28/ 0 赞/ 112 阅读

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

[题目链接][Link 1] 题目大意：读入三个字符串s1，s2，s3，每次将s1和s2字符串依次交叉（s2开始），例如设s1：ABC ，s2：DEF 则第一次交叉后为DAE

矫情吗；*/ 2022年05月18日 07:50/ 0 赞/ 146 阅读

相关 poj 1068 模拟题

呵呵，自己去思考的就是不一样啊！！加油！孩子~ / =============================================

本是古典何须时尚/ 2022年03月29日 06:07/ 0 赞/ 193 阅读

相关 POJ 1006 Biorhythms 模拟

Biorhythms <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

川长思鸟来/ 2022年02月24日 10:58/ 0 赞/ 179 阅读

相关 POJ 3629 队列模拟

听说STL会卡T 然后我就试了一发哈哈哈哈哈哈哈哈哈哈 1000ms卡时过的这很值得我写一发题解了哈哈哈哈哈哈哈哈哈哈哈哈 //By SiriusRen

Myth丶恋晨/ 2021年12月22日 14:17/ 0 赞/ 215 阅读

相关【POJ - 3087】Shuffle'm Up(模拟)

[Shuffle'm Up][Shuffle_m Up] 直接写中文了 Descriptions: 给定两个长度为len的字符串s1和s2，接着给出一个长度为len

我会带着你远行/ 2021年11月26日 17:30/ 0 赞/ 172 阅读