蓝桥杯-九宫重排-bfs+康托展开+逆序数判断

/*
    蓝桥杯-九宫重排
    坑点：用map或set记录状态是否被访问过要logn复杂度
    需要将一个状态按照康托展开，变成一个数字，再用数组记录是否被访问

    再优化：对于一个九宫格，去掉空格那格，若两状态的逆序数奇偶性不同，则无法互相到达
    证明：通过12345678.状态上下左右移动空格，计算逆序数的增减情况，可以知道上下左右移动
    操作的逆序数改变都是偶数，所以，对于一个偶逆序数，不可能到达一个奇逆序数的状态

    当然，在这题中，这个优化并没起到多大作用，可能数据量比较若吧
*/
#include<stdio.h>
#include<string>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
struct Node{
    string stat;
int step;
    Node(){}
    Node(string _stat,int _step):stat(_stat),step(_step){}
};

//map<string,int> vis;//map 或set会超时
int vis[400000 + 5];
string s,e;

int reNum(string x){
int resum = 0;
for(int i = 1;i < 9;i++){
if(x[i] == '.') continue;
//int tmp = 0;
for(int j = 0;j < i;j++){
if(x[j] != '.' && x[j] > x[i]){
//tmp++;
                resum++;
            }
        }
        //printf("tmp[%d] = %d\n",i,tmp);
    }
    //printf("%d\n",resum);
return resum;
}
int conter(string x){
int sum = 0;
for(int i = 0;i < 9;i++){
int num = 0;
for(int j = i+1;j<9;j++){
if(x[j] < x[i]) num++;
        }
        //printf("num = %d\n",num);
        sum = (sum + num) * ((9 - i - 1) == 0 ? 1 : (9 - i - 1));
    }
    //cout<<"x = "<<x<<endl;
//printf("sum = %d\n",sum);
return sum;
}
int change(string &x,int pos,int i){
if(i == 0){
if(pos/3 > 0){
x[pos] = x[pos-3];
x[pos-3] = '.';
return 1;
        }
    }else if(i == 1){
if(pos/3 < 2){
x[pos] = x[pos+3];
x[pos+3] = '.';
return 1;
        }
    }else if(i == 2){
if(pos%3 > 0){
x[pos] = x[pos-1];
x[pos-1] = '.';
return 1;
        }
    }else if(i == 3){
if(pos%3 < 2){
x[pos] = x[pos+1];
x[pos+1] = '.';
return 1;
        }
    }
return 0;
}
int bfs(string s){
    queue<Node> q;
int conter_s = conter(s);
    vis[conter_s] = 1;
q.push(Node(s,0));
while(!q.empty()){
        Node ct = q.front();
q.pop();
if(ct.stat == e){
return ct.step;
        }
int pos;
for(int i = 0;i <= 9;i++){
if(ct.stat[i] == '.'){
pos = i;
break;
            }
        }
for(int i = 0;i < 4;i++){
            string nt = ct.stat;
if(change(nt,pos,i)){
int count_nt = conter(nt);
if(vis[count_nt] == 0){
                    vis[count_nt] = 1;
q.push(Node(nt,ct.step+1));
                }
            }
        }
    }
return -1;
}
int main(){
    memset(vis,0,sizeof(vis));
    cin>>s;
    cin>>e;
int s_resum = reNum(s);
int e_resum = reNum(e);
//printf("%d %d\n",s_resum,e_resum);
if((s_resum%2) != (e_resum%2)){//若两状态逆序数不一样，则肯定无法到达目标状态

printf("-1\n");
    }else{
int ans = bfs(s);
printf("%d\n",ans);
    }
return 0;
}