分析

卡片换位的弱化版

注意：随便什么青蛙和其他真让人迷惑。简单说只考虑个数，不管颜色。

c++ 239ms

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>

#define ffor(i,s,e) for(int i=s;i<e;i++)

using namespace std;
const int M=1e7+12;
int dist[M];
int maxL;

int jump[6]={1,-1,2,-2,3,-3};

int hashi1(string s){
    const char *str=s.c_str();

    int hash=0;
    int seed=133331;
    while(*str){
        hash=hash*seed+(*str++);
    }
    return (hash&0x7fffffff)%M;
}



int hashi(string s){
    const char *str=s.c_str();

    int hash=0;
    for(int i=0;*str;++i){
        if(i&1){
            hash^=(~(11<<hash))^(*str++)^(hash>>3);
        }else {
            hash^=((7<<hash))^(*str++)^(hash>>5);
        }
    }
    return (hash&0x7fffffff)%M;
}

bool check(int nx){
    return nx>=0&&nx<maxL;
}

int bfs(string s,string end){
    queue<string> q;
    q.push(s);
    dist[hashi(s)]=0;

    while(q.size()){
        string now=q.front();q.pop();

        int nowi=hashi(now);
        int nowd=dist[nowi];
        if(now==end){
            return nowd;
        }

        int posX=now.find('*');
        ffor(i,0,6){
            int nx=posX+jump[i];
            if(check(nx)){
                swap(now[nx],now[posX]);
                int nxti=hashi(now);
                if(!dist[nxti]){
                    dist[nxti]=nowd+1;
                    q.push(now);
                }
                swap(now[nx],now[posX]);
            }
        }

    }
    return -1;
}


int main(){
    string start,end;
    getline(cin,start),getline(cin,end);

    maxL=start.size();

    cout<<bfs(start,end)<<endl;
    return 0;
}