蓝桥杯历届试题-九宫重排 （C++代码） 康拓去重+bfs

解题思路:

注意事项:
二维到一维的转化
参考代码:

#include<iostream>

#include<string>

#include<queue>

#include<set>

using namespace std;

struct Node{

int k,d;

string str;

Node(){

}

Node(int k,string str,int d):k(k),str(str),d(d){

}

};

int dr[4]={1,-1,0,0};

int dc[4]={0,0,1,-1};

bool state[362880]; //N的阶乘

bool kangtuo(string x)  //康拓展开进行判重

{

    int fac[]={1,1,2,6,24,120,720,5040,40320};

    int i,j,t,sum;

    sum = 0;

    for(i=0;i<9;i++){

        t = 0;

        for(j=i+1;j<9;j++){

            if(x[j] < x[i])

                t++;

        }

        sum = sum+t*fac[8-i];

    }

    if(state[sum]==1)

        return false;

    else{

        state[sum] = 1;

        return true;

    }

}

int main(){

string s,t;

cin>>s>>t;

int k = s.find('.');

Node start(k,s,0);

queue<Node> q;

q.push(start);

while(!q.empty()){

Node u = q.front();

q.pop();

int index = u.k;

int x = index/3;

int y = index%3;

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

int xx = x + dr[i];

int yy = y + dc[i];

if(xx < 0 || xx >= 3 || yy < 0 || yy>=3) continue;

int id = xx * 3 + yy;

string str = u.str;

char tmp = str[index];

str[index] = str[id];

str[id] = tmp;

int d = u.d + 1;

if(str == t){

cout<<d<<endl;

return 0;

}

if(kangtuo(str)){

q.push(Node(id,str,d));

}

}

}

}