[UVA] 704 Colour Hash

所谓“周界搜索”，练习搜索的好题，双向宽搜/迭代加深均可，还有很多细节有待完善，判重有比set更优的结构，宽搜还没写，先存一下。

//Writer:GhostCai && His Yellow Duck

#include<iostream>

#include<string>

#include<set>

#include<queue>

using namespace std;

set<string> book;

set<string> ans;

bool flag;

string tar="034305650121078709X90";

string st,tmp,sr;

int n;

void change(int way,string &r){

    char sav;

    int i;

    switch(way){

        case 1:

            sav=r[11];

            for(i=11;i>=1;i--) r[i]=r[i-1];

            r[0]=sav;

            break;

        case 2:

            sav=r[0];

            for(i=0;i<=10;i++) r[i]=r[i+1];

            r[11]=sav;

            break;

        case 3:

            sav=r[9];

            for(i=9;i<=19;i++) r[i]=r[i+1];

            r[20]=sav;

            break;

        case 4:

            sav=r[20];

            for(i=20;i>=10;i--) r[i]=r[i-1];

            r[9]=sav;

            break;

    }

}

void make(int dp,int mxdp){

    if(dp>mxdp) return;

    cout<<tar<<endl;

    string pre;

    for(int i=1;i<=4;i++){

        pre=tar;

        change(i,tar);

        if(!ans.count(tar)) {

            ans.insert(tar);

            make(dp+1,mxdp);

        }

        tar=pre;

    }

}

void dfs(int dp,int mxdp){

    if(dp>mxdp) return;

    if(flag) return;

    if(ans.count(tmp)){

        flag=1;

        return;

    }

    if(book.count(tmp) ) return;

//  cout<<tmp<<endl;

    int i;

    string pre;

    for(i=1;i<=4;i++){

        pre=tmp;

        change(i,tmp);

//

            dfs(dp+1,mxdp);

            book.insert(tmp); 

        tmp=pre;

    }

}

bool read_s(){

    int s;

    for(int i=1;i<=24;i++){

        cin>>s;

        if(i>=22) continue;

        if(s==10) st+='X' ;

        else st+=char('0'+s);

    }

    return true;

}

int main(){

    make(1,8);

    cin>>n;

    for(int i=1;i<=n;i++){

//      read_s();

        cin>>st;

//      cout<<st<<endl;

        if(st==tar) {

            cout<<"PUZZLE ALREADY SOLVED\n";

            st="";

            continue;

        }

        tmp=st;

        flag=0;

        for(int i=1;i<=8;i++){

            dfs(1,i);

            if(flag){

                cout<<i<<endl;

                break;

            }

        }

        if(!flag) cout<<"NO SOLUTION WAS FOUND IN 16 STEPS\n";

        st="";

    }

}

巴特西

[UVA] 704 Colour Hash

最新文章

热门文章