[kuangbin带你飞]专题一 简单搜索 G

题目:[kuangbin带你飞]专题一 简单搜索 G

题目大意：扑克牌分成相等两份，两堆依次间隔洗牌，问是否能达到指定的序列，输出第几组测试数据，需要多少次，不能输出-1。

思路

题目一大堆英文，看起来很恐怖，看完之后发现数据量不大且过程不复杂，是一题模拟题，不像搜索题。

• 如何判断无法找到？
  找到之前出现过的序列时还未找到目标序列。
• 如何判断字符串是否出现过？
  使用到map<string,bool>

这种判断无法找到，无法到达，一般使用栈来实现，这样一写就和广搜的写法是一样的，我理解是特殊的广搜题（查找方向只有一个就是shuffle()，只要一碰到访问过的节点，就没有其他方案了直接终止）。

代码实现

#include<iostream>
#include<map>
#include<cstring>
#include<queue>
using namespace std;
map<string,bool> vis;
int C;
int caseNum=1;
string goal;
string merge(string str1,string str2);
struct node{
    string status;
    int steps;
};
string shuffle(string str){

    string str1;
    string str2;
    int i = 0;
    for(i = 0 ;i<C;i++){
        str1+=str[i];
    }
    for(i=C;i<2*C;i++){
        str2+=str[i];
    }
//  cout<<"s1,s2"<<str1<<" "<<str2<<endl;
    return merge(str1,str2);
}


string merge(string str1,string str2){
    string tempstr;
    for(int i = 0 ;i<C;i++){
        tempstr += str2[i];
        tempstr += str1[i];
    }
//  cout<<"s12 "<<tempstr<<endl;
    return tempstr;
}


int bfs(node start){
    queue<node> Q;
    Q.push(start);
    vis[start.status] = true;
    node nownode;
    node nextnode;
    while(!Q.empty()){
        nownode = Q.front();Q.pop();
        if(nownode.status == goal){
            return nownode.steps;
        }
        nextnode.status = shuffle(nownode.status);
//      cout<<"vis "<<vis[nextnode.status]<<endl;
        if(!vis[nextnode.status]){
            vis[nextnode.status] = true;
            nextnode.steps = nownode.steps +1;
            Q.push(nextnode);
        }
        
    }
    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        string s1;
        string s2;
        cin>>C>>s1>>s2>>goal;
        vis.clear();
        node start;
        start.steps = 0;
        start.status = s1+s2;
        cout<<caseNum<<" "<<bfs(start)<<endl;
        caseNum++;
    }   
}

从这一题开始之后的代码都会用到ios::sync_with_stdio(false);
ios::sync_with_stdio(false)的目的是减小cin和cout的耗时
了解更多ios::sync_with_stdio(false)