启发式搜索+康拓展开

#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;

char target[10] = "123804765";
int target_hash;
const int pos[][2]={{1,1},{0,0},{0,1},{0,2},{1,2},{2,2},{2,1},{2,0},{1,0}};
bool vis[500000];
int hashs[10];

struct Node {
    int f,g,h;
    char c[10];
    friend bool operator < (const Node &a,const Node &b){
        if(a.f == b.f) return a.g < b.g;
        return a.f > b.f; 
    }
    
};

/*
void print(const Node &n){
    cout<<"Node: "<<n.f<<" = "<<n.g<<" + "<<n.h<<endl;
    for(int i=0,j;i<3;i++){
        for(j=0;j<3;j++) 
            cout<<n.c[i*3+j]<<" ";
        
        cout<<endl;
    }
    cout<<endl;
}
*/

int unmatch(const char * c){
    int cnt = 0;
    for(int i=0,j;i<3;i++){
        for(j=0;j<3;j++){
            int p = c[i*3+j] - '0';
            if(p == 0) continue;
            //if(abs(pos[p][0] - i) || abs(pos[p][1] - j))
            //cnt+=1;
            cnt+=abs(pos[p][0] - i) + abs(pos[p][1] - j);
        }
    }
    return cnt;
}

int cantor(const char * c){
    int cnt=0,tmp;
    for(int i=0,k;i<9;i++){
        tmp = 0;
        for(k=i-1;k>=0;k--){
            if(c[k]>c[i]) tmp++;
        }
        cnt += hashs[i] * tmp;
    }
    return cnt;
}

bool up(char * c){
    int p0=-1;
    while(1){
        if(c[++p0] == '0') break;
    }
    if(p0>5) return false;
    c[p0] = c[p0+3];
    c[p0+3] = '0';
    return true;
}

bool down(char * c){
    int p0=-1;
    while(1){
        if(c[++p0] == '0') break;
    }
    if(p0<3) return false;
    c[p0] = c[p0-3];
    c[p0-3] = '0';
    return true;
}

bool left(char * c){
    int p0=-1;
    while(1){
        if(c[++p0] == '0') break;
    }
    if(p0%3 == 2) return false;
    c[p0] = c[p0+1];
    c[p0+1] = '0';
    return true;
}

bool right(char * c){
    int p0=-1;
    while(1){
        if(c[++p0] == '0') break;
    }
    if(p0%3 == 0) return false;
    c[p0] = c[p0-1];
    c[p0-1] = '0';
    return true;
}

int search(Node n){
    target_hash = cantor(target);
    if(cantor(n.c) == target_hash) return 0;
    vis[cantor(n.c)]=true;
    memset(vis,0,sizeof(vis));
    priority_queue<Node> que;
    que.push(n);
    while(!que.empty()){
        Node curr = que.top();
        que.pop();
    
        Node set[4];
        set[0]=set[1]=set[2]=set[3]=curr;
        up(set[0].c);left(set[1].c);down(set[2].c);right(set[3].c);
        for(int i=0;i<4;i++){
            set[i].g=curr.g+1;
            set[i].h=unmatch(set[i].c);
            set[i].f=set[i].g+set[i].h;
            int t = cantor(set[i].c);
            //cout<<i<<" "<<t<<":"<<endl;
            //print(set[i]);
            if(t == target_hash) return set[i].g;
            if(!vis[t]){
                vis[t] = true;
                que.push(set[i]);
                //cout<<"pushed"<<endl<<endl;
            }
        }
    }
}

int main(){
    
    hashs[0]=1;
    for(int i=1;i<11;i++){
        hashs[i] = hashs[i-1] * i;
    }
    Node start;
    cin>>start.c;
    //strcpy(start.c,"203184765");
    start.g=0;
    start.h=unmatch(start.c);
    start.f=start.g+start.h;
    //print(start);
    cout<<search(start);
    return 0;
} 

简单的搜索题写这么久...我是真的菜

#include <stdio.h>

long queue[100000][2] = {0};
const int goal[9] = {1, 2, 3, 8, 0, 4, 7, 6, 5};
long goalLong;
const short pInt[9][4] = {{1, 3, -1, -1},
                          {0, 2, 4,  -1},
                          {1, 5, -1, -1},
                          {0, 4, 6,  -1},
                          {1, 3, 5,  7},
                          {2, 4, 8,  -1},
                          {3, 7, -1, -1},
                          {6, 8, 4,  -1},
                          {5, 7, -1, -1}};
long frac_array[10];

long frac(int n) {
    if (n == 0) return 1;
    return frac_array[n] ? frac_array[n] : (frac_array[n] = n * frac(n - 1));
}

long cantor(const int *array, int n) {
    long answer = 0;
    for (int i = 0; i < n; i++) {
        int index = 0;
        for (int j = i + 1; j < n; j++)
            if (array[i] > array[j])index++;
        answer += frac(n - i - 1) * index;
    }
    return answer;
}

void revCantor(long expanded, int n, int array[n]) {
    int used[100] = {0};
    for (int i = 0; i < n; i++) {
        array[i] = expanded / frac(n - i - 1) + 1;
        for (int j = 0; j < n; j++) {
            if (used[j] == 0) {
                array[i]--;
                if (array[i] == 0) {
                    array[i] = j;
                    used[j] = 1;
                    break;
                }
            }
        }
        expanded %= frac(n - i - 1);
    }
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

char contain(long expanded, int tail) {
    for (int i = 0; i < tail - 1; i++) {
        if (expanded == queue[i][0]) {
            return 1;
        }
    }
    return 0;
}

/*
 * 0 1 2
 * 3 4 5
 * 6 7 8
 *
 * */
int main() {
    int input_array[9];
    goalLong = cantor(goal, 9);
    revCantor(goalLong, 9, input_array);
    for (short i = 0; i < 9; i++) {
        input_array[i] = getchar() - '0';

    }
    queue[0][0] = cantor(input_array, 9);
    queue[0][1] = 0;
    if (queue[0][0] == goalLong) {
        putchar('0');
        return 0;
    }
    //宽度优先搜索
    int head = 0, tail = 1;
    while (head < tail) {
        int tmp_array[9] = {0};
        revCantor(queue[head][0], 9, tmp_array);
        int zeroIndex = 0;
        for (int i = 0; i < 9; i++) {
            if (tmp_array[i] == 0) {
                zeroIndex = i;
                break;
            }
        }
        //四方向扩展
        for (int i = 0; i < 4; i++) {
            if (pInt[zeroIndex][i] >= 0) {
                swap(&tmp_array[zeroIndex], &tmp_array[pInt[zeroIndex][i]]);

                long c = cantor(tmp_array, 9);
                if (!contain(c, tail)) {
                    queue[tail][0] = c;
                    queue[tail][1] = queue[head][1] + 1;
                    if (queue[tail][0] == goalLong) {
                        printf("%ld", queue[tail][1]);
                        return 0;
                    }
                    tail++;
                }

                swap(&tmp_array[zeroIndex], &tmp_array[pInt[zeroIndex][i]]);
            }
        }
        head++;
    }
    return 0;
}

1.利用stirng来表示状态
2.利用<unordered_map> 可以更容易地判断路径重复和记录距离
3./x %x 来一维转二维

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

int bfs(string state)
{
    queue<string> q;
    unordered_map<string, int> d;

    q.push(state);
    d[state] = 0;

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

    string end = "123804765";
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        if (t == end) return d[t];

        int distance = d[t];
        int k = t.find('0');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);
            }
        }
    }

    return -1;
}

int main()
{
    string state;
    cin>>state;

    cout << bfs(state) << endl;

    return 0;
}

bfs一下

#include<cstdio>
#include<cstring>
#include<set>
using namespace std;

typedef int State[9];
const int MAXSTATE=1000000;
State st[MAXSTATE],goal={1,2,3,8,0,4,7,6,5};
int dist[MAXSTATE];

set<int> vis;
void init_lookup_table() { vis.clear(); }
int try_to_insert(int s)
{
    int v=0;
    for(int i=0;i<9;i++) v=v*10+st[s][i];
    if(vis.count(v)) return 0;
    vis.insert(v);
    return 1;
}

const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int bfs()
{
    init_lookup_table();
    int front=1,rear=2;
    while(front<rear)
    {
        State& s=st[front];
        if(memcmp(goal,s,sizeof(s))==0) return front;
        int z;
        for(z=0;z<9;z++) if(!s[z]) break;
        int x=z/3,y=z%3;
        for(int d=0;d<4;d++)
        {
            int newx=x+dx[d];
            int newy=y+dy[d];
            int newz=newx*3+newy;
            if(newx>=0 && newx<3 && newy>=0 && newy<3)
            {
                State& t=st[rear];
                memcpy(&t,&s,sizeof(s));
                t[newz]=s[z];
                t[z]=s[newz];
                dist[rear]=dist[front]+1;
                if(try_to_insert(rear)) rear++;
            }
        }
        front++;
    }
    return 0;
}

int main()
{
    char s[15];
    scanf("%s",s);
    for(int i=0;i<9;i++)
        st[1][i]=s[i]-'0';
//  for(int i=0;i<9;i++) printf(" %d ",st[1][i]); 
    int ans = bfs();
    printf("%d\n", dist[ans]);
    return 0;
}

第一次一次性AC，热泪盈眶

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int up(int i){
    if(i-3>=0) return i-3;
    else return -1;
}
int down(int i){
    if(i+3<9) return i+3;
    else return -1;
}
int left(int i){
    if(i%3==0) return -1;
    else return i-1;
}
int right(int i){
    if(i%3==2) return -1;
    else return i+1;
}
queue<string> q;
map<string,int> s;
string t="1238047654";
int bfs(){
    int pos,z;
    string a,b;
    while(!q.empty()){
        a = q.front(); q.pop();
        z = a[9]-'0';
        if((pos=up(z))!=-1){
            b = a;
            swap(b[z],b[pos]);
            b[9] = pos+'0';
            if(!s.count(b)) s[b] = s[a]+1, q.push(b);
            if(b==t) return s[b];
        }
        if((pos=down(z))!=-1){
            b = a;
            swap(b[z],b[pos]);
            b[9] = pos+'0';
            if(!s.count(b)) s[b] = s[a]+1, q.push(b);
            if(b==t) return s[b];
        }
        if((pos=left(z))!=-1){
            b = a;
            swap(b[z],b[pos]);
            b[9] = pos+'0';
            if(!s.count(b)) s[b] = s[a]+1, q.push(b);
            if(b==t) return s[b];
        }
        if((pos=right(z))!=-1){
            b = a;
            swap(b[z],b[pos]);
            b[9] = pos+'0';
            if(!s.count(b)) s[b] = s[a]+1, q.push(b);
            if(b==t) return s[b];
        }
    }
}
int main()
{
    string a;
    cin >> a;
    int z;
    for(int i=0; i<a.size();i++){
        if(a[i]=='0'){
            z = i;
            break;
        }
    }
    a += z+'0';
    q.push(a);
    s[a] = 0;
    cout << bfs();
    return 0;
}

#include<stdio.h>
#include<stdlib.h>
using namespace std;

//算法思想：宽度优先搜索，从两头向中间接近，直到相遇
//宽搜队列，每一个状态的节点

struct node{
short a[10];//状态
short zero;//零点位置
short fore; //上一步的操作
short step; //搜索树层数（操作了多少步）
node *next;
};
//题目中给出的移动方式，可以等效于零点向四个方向移动
//依据x定出移动方向，对head节点中的零点做移动，存到tail节点中
//x:1上；2，下；3，左；4，右
void move(node *head, node *tail, short x)
{
int k,i;
for(i=1;i<=9;i++)
tail->a[i]=head->a[i];
tail->zero=head->zero;
tail->step=head->step+1;
i=tail->zero;
switch(x)
{
case 1:{
tail->zero-=3;
k=tail->a[i-3];
tail->a[i-3]=tail->a[i];
tail->a[i]=k;
tail->fore=2;
break;
}
case 2:{
tail->zero+=3;
k=tail->a[i+3];
tail->a[i+3]=tail->a[i];
tail->a[i]=k;
tail->fore=1;
break;
}
case 3:{
tail->zero-=1;
k=tail->a[i-1];
tail->a[i-1]=tail->a[i];
tail->a[i]=k;
tail->fore=4;
break;
}
case 4:{
tail->zero+=1;
k=tail->a[i+1];
tail->a[i+1]=tail->a[i];
tail->a[i]=k;
tail->fore=3;
break;
}
}
}
//判断零点在x，移动方向是y，能否移动（是否越界）

bool movable(int x,int y)
{
switch(y)
{
case 1:{
if(x<4) return 0;
break;
}
case 2:{
if(x>6) return 0;
break;
}
case 3:{
if(x%3==1) return 0;
break;
}
case 4:{
if(x%3==0) return 0;
break;
}
}
return 1;
}
//九进制hash函数
//每个状态可以用一个九进制九位数来表示
unsigned long hash(node *p)
{
int n,i;
//最小的一状态，粗略记录为九进制下的012000000
const int min_hash=63412811;
n=0;
for(i=1;i<=9;i++)
{
n=n*9;//九进制数，不断进位
n+=p->a[i];
}
n-=min_hash;
return n;
}

//二分查找树，a用于储存九进制表示的节点状态
struct node2{
unsigned long a;
short step;
node2 *left;
node2 *right;
};

//在二分查找树中搜索一个节点，如果找到，返回1；没有找到则插入该节点并返回0
bool search_insert(unsigned long a,node2 *head,short step)
{
node2 *p,*q;
p=head;
q=p;
//大于该父节点则插入右分支，小于父节点则插入左分支。
//寻找节点
//step记录每个节点是经过了多少步的搜索
while(q!=NULL)
{
p=q;
if(a<p->a) q=p->left;
if(a>p->a) q=p->right;
if(a==p->a) return 1;
}
//插入节点
if(a<p->a)
{
p->left=new node2;
q=p->left;
}
if(a>p->a)
{
p->right=new node2;
q=p->right;
}
q->a=a;
q->step=step;
q->left=NULL;
q->right=NULL;
return 0;
}
//在查找树中搜索一个节点。没找到返回0，找到则返回该节点经历了多少步搜索。
short search(unsigned long a,node2 *head)
{
node2 *p,*q;
short step;
p=head;
q=p;
while(q!=NULL)
{
p=q;
if(a<p->a) q=p->left;
if(a>p->a) q=p->right;
if(a==p->a)
{
step=p->step;
return step;
}
}
return 0;
}
//递归删除二叉查找树
void release(node2 *p)
{
if(p->left!=NULL)
release(p->left);
if(p->right!=NULL)
release(p->right);
delete p;

}

int main()
{
//head1,tail1是从起点出发的宽搜队列；head2,tail2是从终点出发的宽搜队列。p是过渡用的变量
node *head1,*tail1,*head2,*tail2,*p;
int i,j,k;//循环变量
//记录目前搜索到的状态值，l0是两棵搜索树相遇的位置

unsigned long l,l0;
char ch;
//hash1,从起点开始搜索产生的查找树；hash2，从终点搜索产生的查找树。
node2 *hash1, *hash2;
//题目中所给的目标状态，a[0]=9纯粹是为了占位置。
int a[10]={9,1,2,3,8,0,4,7,6,5};
short b=0; //b=0 没有完成任务，b>0表示完成了任务
short step; //用于记录步数，过渡用变量

//初始情况，存入宽搜队列
head1=new node;
for(i=1;i<=9;i++)
{
scanf("%c",&ch);
k=(short) (ch-'0');
head1->a[i]=k;
if(k==0) head1->zero=i;
}
head1->fore=0;
head1->step=0;
head1->next=NULL;
tail1=head1;
//初始情况加入查找树
hash1=new node2;
hash1->left=NULL;
hash1->right=NULL;
l=hash(head1);
hash1->a=l;
//目标节点存入宽搜队列
head2=new node;
for(i=1;i<=9;i++)
head2->a[i]=a[i];
head2->zero=5;
head2->fore=0;
head2->step=0;
head2->next=NULL;
tail2=head2;
//目标节点加入查找树
hash2=new node2;
hash2->left=NULL;
hash2->right=NULL;
l=hash(head2);
hash2->a=l;
//先操作初始队列，后操作返回队列，最后判断是否相遇
while(b==0)
{
//从前向后搜索
//head节点上一步的反向操作，这一剪枝，以免进入死循环。
k=(int) head1->fore;
//head节点零点位置，用于判断移动方向
j=(int) head1->zero;
for(i=1;i<=4;i++)
if((i!=k)&&(movable(j,i)==1))//可以移动
{
p=new node;
move(head1,p,i);
l=hash(p);
step=p->step;
if(search_insert(l,hash1,step)==1)
delete p;
else {
tail1->next=p;
tail1=p;
p->next=NULL;
}

}
//释放刚刚拓展过的节点
p=head1;
head1=head1->next;
delete p;

//从后向前搜索，步骤与从前向后搜索相同

k=(int) head2->fore;
j=(int) head2->zero;
for(i=1;i<=4;i++)

if((i!=k)&&(movable(j,i)==1))
{
p=new node;
move(head2,p,i);
l=hash(p);
step=p->step;
if(search_insert(l,hash2,step)==1)
delete p;
else

{
tail2->next=p;
p->next=NULL;
tail2=p;

}
b=search(l,hash1);
if(b>0){
l0=l;
break;
}

}

//释放搜索过的节点
p=head2;
head2=head2->next;
delete p;
}
//从起点搜索了多少步，从终点搜索了多少步，相加即为总步数
k=(int)search(l0,hash1)+(int)search(l0,hash2);
printf("%d\n",k);
//释放队列
while(head1!=NULL)
{
p=head1;
head1=head1->next;
delete p;
}
while(head2!=NULL)
{
p=head2;
head2=head2->next;
delete p;
}
//释放查找树
release(hash1);
release(hash2);
}

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
#include <string.h>
#include <ctype.h>
#define max(a, b) (a > b ? a : b)
#define MOD 100007
#define MAX_SIZE 524288

int adj[9][9] = {{0, 1, 0, 1, 0, 0, 0, 0, 0},
                 {1, 0, 1, 0, 1, 0, 0, 0, 0},
                 {0, 1, 0, 0, 0, 1, 0, 0, 0},
                 {1, 0, 0, 0, 1, 0, 1, 0, 0},
                 {0, 1, 0, 1, 0, 1, 0, 1, 0},
                 {0, 0, 1, 0, 1, 0, 0, 0, 1},
                 {0, 0, 0, 1, 0, 0, 0, 1, 0},
                 {0, 0, 0, 0, 1, 0, 1, 0, 1},
                 {0, 0, 0, 0, 0, 1, 0, 1, 0}};

typedef struct item {
    int value;
    int step;
    int cost;
}Item;

typedef struct pq {
    Item *items;
    int nitems;
    int nspots;
} *PQ, PQrep;

typedef int KEYS; 

typedef struct tree {
    struct tree *left, *right;
    KEYS value;
    int hi;
} *BST, BSTrep;

typedef struct maps {
    BST *keys;
    int nkeys;
} *Maps, Maprep; 
// the hashing ADT
int searchKey(Maps h, KEYS value);
BST newBSTnode(KEYS value);
BST insertBST(BST t, KEYS value);
void insertKey(Maps h, KEYS value);
Maps newHash();
int searchBST(BST t, KEYS value);
int cmp(KEYS value1, KEYS value2);
void dropMaps(Maps h);
void dropBST(BST t);
int height(BST t);
BST rebalance(BST t);
void showMaps(Maps h);
// the priorityQueue ADT
PQ newPQ(void);
void insertPQ(PQ q, Item newitem);
void floatup(PQ q, int index);
int highpriority(Item v1, Item v2);
void swap(PQ q, int index1, int index2);
int qempty(PQ q);
Item pop(PQ q);
void floatdown(PQ q, int index);
void showPQ(PQ q, int index, int depth);
void freePQ(PQ q);
// the A_star algrithum
void A_Star(int, int);
int hcost(int curr, int dest);

int main() {
    int end;
    scanf("%d", &end);
    A_Star(123804765, end);
    return 0;
}

void A_Star(int start, int dest) {
    PQ q = newPQ();
    Maps h = newHash();
    Item newitem, nextitem;
    char *str, *tmp, tp; 
    int reachable[9], size, i, len, index;
    
    newitem.step = 0;
    newitem.value = start;
    newitem.cost = hcost(start, dest);
    insertPQ(q, newitem);
    while (!qempty(q)) {
        newitem = pop(q);
        
        if (newitem.value == dest) {
            printf("%d\n", newitem.step);
            return;
        }
        
        if (searchKey(h, newitem.value)) {
            continue;
        }
        
        insertKey(h, newitem.value);
        str = (char *) calloc(11, sizeof(char));
        tmp = (char *) calloc(11, sizeof(char));
        if (newitem.value < 1e8) {
            str[0] = '0';
            sprintf(tmp, "%d", newitem.value);
            strcat(str, tmp);
        } else {
            sprintf(str, "%d", newitem.value);
        }
        
        size = 0;
        len = strlen(str);
        
        for (i = 0 ; i < len; i++) {
            if (str[i] == '0') {
                index = i;
                break;
            }
        }
        
        for (i = 0 ; i < len; i++) {
            if (adj[i][index] == 1) {
                strcpy(tmp, str);
                tp = tmp[index];
                tmp[index] = tmp[i];
                tmp[i] = tp;
                reachable[size++] = atoi(tmp);
            }
        }
        
        free(str);
        free(tmp);
        for (i = 0 ; i < size; i++) {
            if (!searchKey(h, reachable[i])) {
                nextitem.value = reachable[i];
                nextitem.step = 1 + newitem.step;
                nextitem.cost = newitem.step + hcost(reachable[i], dest); 
                insertPQ(q, nextitem);
            }
        }
        /*
            for value in reachable items and items not in hashing map {
                nextitem.value = value;
                nextitem.step = 1 + newitem.step;
                nextitem.cost = newitem.step + hcost(value, dest); 
                insertPQ(PQ, nextitem);
            } 
        */
    }
}



int hcost(int curr, int dest) {
    char *str1, *str2, *tmp;
    int count = 0, i;
    str1 = (char *) calloc(11, sizeof(char));
    str2 = (char *) calloc(11, sizeof(char));
    tmp = (char *) calloc(11, sizeof(char));
    if (curr < 1e8) {
        str1[0] = '0';
        sprintf(tmp, "%d", curr);
        strcat(str1, tmp);
    } else {
        sprintf(str1, "%d", curr);
    }
    free(tmp);
    tmp = (char *) calloc(11, sizeof(char));
    if (dest < 1e8) {
        str2[0] = '0';
        sprintf(tmp, "%d", dest);
        strcat(str2, tmp);
    } else {
        sprintf(str2, "%d", dest);
    }
    free(tmp);
    int len = strlen(str1);
    for (i = 0 ; i < len; i++) {
        if (str1[i] != str2[i]) count++;
    }
    
    free(str1);
    free(str2);
    return count;
}

Maps newHash() {
    Maps h = (Maps) calloc(1, sizeof(Maprep));
    h->nkeys = MOD;
    h->keys = (BST *) calloc(h->nkeys + 1, sizeof(BST));
    int i;
    for (i = 0 ; i < h->nkeys; i++) {
        h->keys[i] = NULL;
    }
    return h;
}

BST newBSTnode(KEYS value) {
    BST node = (BST) malloc(sizeof(BSTrep));
    node->left = NULL;
    node->right = NULL;
    node->value = value;
    node->hi = 0;
    return node;
}

int cmp(KEYS value1, KEYS value2) {
    if (value1 == value2) return 0;
    if (value1 < value2) return -1;
    return 1;
}

int searchBST(BST t, KEYS value) {
    if (t == NULL) return 0;
    if (cmp(t->value, value) == 0) return 1;
    if (cmp(t->value, value) == -1) return searchBST(t->right, value);
    return searchBST(t->left, value);
}

int searchKey(Maps h, KEYS value) {
    return searchBST(h->keys[value % MOD], value);
}

BST leftRotate(BST t) {
    if (t == NULL || t->right == NULL) return t;
    BST tmp = t->right;
    t->hi = max(height(t->left), height(tmp->left)) + 1;
    t->right = tmp->left;
    tmp->left = t;
    tmp->hi = max(height(tmp->left), height(tmp->right)) + 1;
    return tmp;
}

BST rightRotate(BST t) {
    if (t == NULL || t->left == NULL) return t;
    BST tmp = t->left;
    t->hi = max(height(t->right), height(tmp->right)) + 1;
    t->left = tmp->right;
    tmp->right = t;
    tmp->hi = max(height(tmp->right), height(tmp->left)) + 1;
    return tmp;
}

BST rebalance(BST t) {
    if (t == NULL) return t;
    if (height(t->left) - height(t->right) > 1) {
        if (height(t->left->left) > height(t->left->right)) {
            t = rightRotate(t);
        } else if(height(t->left->left) < height(t->left->right)) {
            t->left = leftRotate(t->left);
            t = rightRotate(t);
        }
    } else if (height(t->right) - height(t->left) > 1) {
        if (height(t->right->left) > height(t->right->right)) {
            t->right = rightRotate(t->right);
            t = leftRotate(t);
        } else if (height(t->right->left) < height(t->right->right)) {
            t = leftRotate(t);
        }
    }
    return t;
}

int height(BST t) {
    if (t == NULL) return -1;
    return t->hi;
}

BST insertBST(BST t, KEYS value) {
    if (t == NULL) return newBSTnode(value);
    if (cmp(t->value, value) == 0) return t;
    if (cmp(t->value, value) == -1) t->right = insertBST(t->right, value);
    else t->left = insertBST(t->left, value);
    t->hi = max(height(t->left), height(t->right)) + 1;
    t = rebalance(t);
    t->hi = max(height(t->left), height(t->right)) + 1;
    return t; 
}

void insertKey(Maps h, KEYS value) {
    h->keys[value % MOD] = insertBST(h->keys[value % MOD], value);
}

void dropBST(BST t) {
    if (t != NULL) {
        dropBST(t->left);
        dropBST(t->right);
        free(t);
    }
}

void dropMaps(Maps h) {
    int i;
    for (i = 0 ; i < h->nkeys; i++) {
        dropBST(h->keys[i]);
    }
    free(h);
}

void showBST(BST h, int level) {
    if (h == NULL) return;
    int i;
    showBST(h->right, level + 1);
    for (i = 0 ; i < level; i++) printf("\t\t");
    printf("%d\n", h->value);
    showBST(h->left, level + 1);
}

void showMaps(Maps h) {
    int i;
    for (i = 0 ; i < h->nkeys; i++) {
        if (h->keys[i] != NULL) {
            printf("the %dth key is\n", i);
            showBST(h->keys[i], 0);
            printf("\n");
        }
    }
}


void freePQ(PQ q) {
    free(q->items);
    free(q);
}

PQ newPQ() {
    PQ q = (PQ) calloc(1, sizeof(PQrep));
    q->items = (Item *) calloc(1 + MAX_SIZE, sizeof(Item));
    q->nspots = MAX_SIZE;
    q->nitems = 0;
    return q;
}

int highpriority(Item v1, Item v2) {
    return (v1.cost < v2.cost);
}

void swap(PQ q, int index1, int index2) {
    Item tmp;
    tmp = q->items[index1];
    q->items[index1] = q->items[index2];
    q->items[index2] = tmp;
}

void floatup(PQ q, int index) {
    if (index <= 1) return;
    if (highpriority(q->items[index], q->items[index / 2])) {
        swap(q, index, index / 2);
        floatup(q, index / 2);
    }
}

void insertPQ(PQ q, Item newitem) {
    if (q->nitems >= q->nspots) return;
    q->items[++q->nitems] = newitem;
    floatup(q, q->nitems);
}

int qempty(PQ q) {
    return (q->nitems <= 0);
}

void floatdown(PQ q, int index) {
    if (q->nitems  < index * 2 + 1) return;
    if (q->nitems >= 2 * index + 1) {
        if (highpriority(q->items[index * 2], q->items[index * 2 + 1])) {
            if (highpriority(q->items[index * 2], q->items[index])) {
                swap(q, index * 2, index);
                floatdown(q, index * 2);
            }
        } else {
            if (highpriority(q->items[index * 2 + 1], q->items[index])) {
                swap(q, index * 2 + 1, index);
                floatdown(q, index * 2 + 1);
            }
        }
    } else if (q->nitems >= 2 * index) {
        if (highpriority(q->items[index * 2], q->items[index])) {
            swap(q, index * 2, index);
            floatdown(q, index * 2);
        }
    }
}

Item pop(PQ q) {
    assert(q != NULL);
    assert(q->items != NULL);
    assert(!qempty(q));
    Item value = q->items[1];
    swap(q, 1, q->nitems);
    q->nitems--;
    floatdown(q, 1);
    return value;   
}

void showPQ(PQ q, int index, int depth) {
    assert(q != NULL);
    if (q->nitems < index) return;
    showPQ(q, index * 2 + 1, depth + 1);
    int i;
    for (i = 0 ; i < depth; i++) printf("\t\t");
    printf("%d\n", q->items[index].value);
    showPQ(q, index * 2, depth + 1);
}

方法一：BFS+队列式分支界限优化+STL节约空间

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#define INIT 400000
using namespace std;

struct eight
{
    bool b;
    int sum;
    eight():b(false),sum(0)
    {

    }
};
int ans=INIT;
map<string,eight> judge;
queue<string> q;

void BFS(const string& str)
{
    string t;
    judge[str].b=true;
    q.push(str);
    while(q.empty()==false)
    {
        t=q.front();
        q.pop();
        if(t=="123804765")
            ans=min(ans,judge[t].sum);
        else if(judge[t].sum<ans)
        {
            int loc=t.find('0');
            int x=loc/3;
            int y=loc%3;
            int step=judge[t].sum;
            if(x-1>=0)
            {
                swap(t[loc],t[loc-3]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    q.push(t);
                }
                swap(t[loc],t[loc-3]);
            }
            if(y-1>=0)
            {
                swap(t[loc],t[loc-1]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    q.push(t);
                }
                swap(t[loc],t[loc-1]);
            }
            if(y+1<=2)
            {
                swap(t[loc],t[loc+1]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    q.push(t);
                }
                swap(t[loc],t[loc+1]);
            }
            if(x+1<=2)
            {
                swap(t[loc],t[loc+3]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    q.push(t);
                }
                swap(t[loc],t[loc+3]);
            }
        }
    }
}

int main()
{
    string str;
    cin>>str;
    if(str=="123804765")
        cout<<0<<endl;
    else
        BFS(str);
    if(ans==INIT)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    return 0;
}

方法二：BFS+A*+STL节约空间

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#define INIT 400000
using namespace std;

const string des="123804765";
struct eight
{
    bool b;
    int sum;
    int num;
    eight():b(false),sum(0),num(0)
    {

    }
};
int ans=INIT;
map<string,eight> judge;
struct cmp
{
    bool operator () (const string& a,const string& b)
    {
        return judge[a].num>judge[b].num;
    }
};
priority_queue<string,vector<string>,cmp> q;

void cal_num(const string& t)
{
    int c=0;
    for(int i=0;i<9;i++)
        if(t[i]!=des[i])
            c++;
    judge[t].num=c+judge[t].sum;
}

void BFS(const string& str)
{
    string t;
    judge[str].b=true;
    cal_num(str);
    q.push(str);
    while(q.empty()==false)
    {
        t=q.top();
        q.pop();
        if(t==des)
            ans=min(ans,judge[t].sum);
        else if(judge[t].sum<ans)
        {
            int loc=t.find('0');
            int x=loc/3;
            int y=loc%3;
            int step=judge[t].sum;
            if(x-1>=0)
            {
                swap(t[loc],t[loc-3]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    cal_num(t);
                    q.push(t);
                }
                swap(t[loc],t[loc-3]);
            }
            if(y-1>=0)
            {
                swap(t[loc],t[loc-1]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    cal_num(t);
                    q.push(t);
                }
                swap(t[loc],t[loc-1]);
            }
            if(y+1<=2)
            {
                swap(t[loc],t[loc+1]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    cal_num(t);
                    q.push(t);
                }
                swap(t[loc],t[loc+1]);
            }
            if(x+1<=2)
            {
                swap(t[loc],t[loc+3]);
                if(judge[t].b==false)
                {
                    judge[t].b=true;
                    judge[t].sum=step+1;
                    cal_num(t);
                    q.push(t);
                }
                swap(t[loc],t[loc+3]);
            }
        }
        if(judge[q.top()].num>=ans)
            break;
    }
}

int main()
{
    string str;
    cin>>str;
    if(str==des)
        cout<<0<<endl;
    else
        BFS(str);
    if(ans==INIT)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    return 0;
}

#include <iostream>
using namespace std;
#define INF 0x7fffffff
char Koma[3][3]={{'1','2','3'},{'8','0','4'},{'7','6','5'}};
int num=INF;
struct team
{
char Base[3][3];
};
void Change(char & a,char & b)
{
char x;
x=a;
a=b;
b=x;
}
bool Check(team h)
{
for(int a=0;a<3;a++)
for(int b=0;b<3;b++)
if(h.Base[a][b]!=Koma[a][b])
return 0;
return 1;
}
int bfs(team h,int count,int repead)
{
if(Check(h))
{
if(count<num)
num=count;
/*for(int a=0;a<3;a++)
{
for(int b=0;b<3;b++)
cout<<h.Base[a][b]<<" ";
cout<<endl;
}
*/
return 0;
}
if(count>=22)
return 0;
for(int a=0;a<3;a++)
for(int b=0;b<3;b++)
if(h.Base[a][b]=='0')
{
if(a-1>=0&&repead!=7)
{
Change(h.Base[a-1][b],h.Base[a][b]);
bfs(h,count+1,2);
Change(h.Base[a-1][b],h.Base[a][b]);
}
if(b-1>=0&&repead!=5)
{
Change(h.Base[a][b-1],h.Base[a][b]);
bfs(h,count+1,4);
Change(h.Base[a][b-1],h.Base[a][b]);
}
if(b+1<3&&repead!=4)
{
Change(h.Base[a][b+1],h.Base[a][b]);
bfs(h,count+1,5);
Change(h.Base[a][b+1],h.Base[a][b]);
}
if(a+1<3&&repead!=2)
{
Change(h.Base[a+1][b],h.Base[a][b]);
bfs(h,count+1,7);
Change(h.Base[a+1][b],h.Base[a][b]);
}
}
}
int main()
{
team h;
for(int a=0;a<3;a++)
for(int b=0;b<3;b++)
cin>>h.Base[a][b];
bfs(h,0,0);
cout<<num;
}

之前《人工智能导论》课程的作业，采用面向对象方法设计的程序。

#include <fstream>
#include <iostream>
#include <cstring>

using namespace std;

class StatusHeap;

struct Status
{
    int matrix[9] = {0};
    int key = 0, f = 0, g = 0, h = 0, pos0 = 0;
    Status* p = nullptr;

    Status() = default;
    explicit Status(Status*);
    ~Status() = default;

    void calcf();   // 计算 f 值
    int calckey();  // 计算康拓展开的 hash 值，进行查重

    void print(std::ostream &);

    Status* canGo(StatusHeap *, StatusHeap *, int);

    Status* canGoL(StatusHeap *, StatusHeap *); // “0”可以向左走，下面三个函数同理
    Status* canGoR(StatusHeap *, StatusHeap *);
    Status* canGoU(StatusHeap *, StatusHeap *);
    Status* canGoD(StatusHeap *, StatusHeap *);
};

class StatusHeap
{
private:
    Status *h[370000] = {nullptr};      // Status 指针数组
    bool hasit[370000] = {false};       // 用康拓展开 hash 判断是否在堆中
    int size;

protected:
    int properParent(int);

public:
    StatusHeap();
    ~StatusHeap();

    int Size();

    void insert(Status *s);

    Status *delMax();

    bool inHeap(int k);
};

// 康拓展开用 0!, 1!, ..., 8!
static const int fac[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};

// 构造函数，拷贝matrix，记录父节点
Status::Status(Status* pp)
{
    p = pp;
    if(p) g = p->g + 1; else g = 0;
    if(p)
    {
        for(int i = 0; i < 9; ++i)
            matrix[i] = p->matrix[i];
        pos0 = p->pos0;
    }
}

void Status::calcf()
{
    h = 0;
    if(matrix[0] != 1) h++;
    if(matrix[1] != 2) h++;
    if(matrix[2] != 3) h++;
    if(matrix[3] != 8) h++;
    if(matrix[5] != 4) h++;
    if(matrix[6] != 7) h++;
    if(matrix[7] != 6) h++;
    if(matrix[8] != 5) h++;
    f = g + h;
}

int Status::calckey()
{
    int x = 0, count;
    for(int i = 0; i < 9; ++i)
    {
        count = 0;
        for(int j = i + 1; j < 9; ++j)
            if(matrix[i] < matrix[j]) ++count;
        x += count * fac[8 - i];
    }
    return x;
}

void Status::print(ostream &fout)
{
    // 先打印父节点，再打印自己
    if(p && p->p) p->print(fout);
    fout << endl;
    fout << matrix[0] << ' ' << matrix[1] << ' ' << matrix[2] << endl;
    fout << matrix[3] << ' ' << matrix[4] << ' ' << matrix[5] << endl;
    fout << matrix[6] << ' ' << matrix[7] << ' ' << matrix[8] << endl;
}

Status* Status::canGoL(StatusHeap *open, StatusHeap *close)
{
    // 如果“0”在第一列，则无法向左移。下面三个函数同理
    if(pos0 % 3 == 0) return nullptr;
    return canGo(open, close, -1);
}

Status* Status::canGoR(StatusHeap *open, StatusHeap *close)
{
    if(pos0 % 3 == 2) return nullptr;
    return canGo(open, close, 1);
}

Status* Status::canGoU(StatusHeap *open, StatusHeap *close)
{
    if(pos0 / 3 == 0) return nullptr;
    return canGo(open, close, -3);
}

Status* Status::canGoD(StatusHeap *open, StatusHeap *close)
{
    if(pos0 / 3 == 2) return nullptr;
    return canGo(open, close, 3);
}

// 如果“0”可以移动，则调用此函数查重
Status* Status::canGo(StatusHeap *open, StatusHeap *close, int delta)
{
    // 移动数字块并重新计算key
    int x = matrix[pos0 + delta];
    matrix[pos0 + delta] = matrix[pos0];
    matrix[pos0] = x;
    int k = calckey();

    // 如果节点已出现过，则换回来，否则新建节点并返回指针
    if(open->inHeap(k) || close->inHeap(k))
    {
        x = matrix[pos0 + delta];
        matrix[pos0 + delta] = matrix[pos0];
        matrix[pos0] = x;
        return nullptr;
    } else {
        auto *newnode = new Status(this);

        x = matrix[pos0 + delta];
        matrix[pos0 + delta] = matrix[pos0];
        matrix[pos0] = x;
        newnode->key = newnode->calckey();

        newnode->pos0 = pos0 + delta;
        newnode->calcf();

        return newnode;
    }
}


int StatusHeap::properParent(int i)
{
    int pf = h[i]->f, l = 1 + (i << 1), r = (i + 1) << 1;
    if(l >= size)
        return i;
    else
    {
        int lf = h[l]->f;
        if(r >= size)
        {
            if(pf > lf)
                return l;
            else
                return i;
        } else {
            int rf = h[r]->f;
            if((pf <= lf) && (pf <= rf))
                return i;
            else
            {
                if((lf < pf) && (lf <= rf))
                    return l;
                else
                    return r;
            }
        }
    }
}

StatusHeap::StatusHeap() { size = 0; memset(hasit, 0, sizeof(bool) * 370000); }
StatusHeap::~StatusHeap() { for(int i = 0; i < size; ++i) delete h[i]; }

int StatusHeap::Size() { return size; }

// 堆插入
void StatusHeap::insert(Status *s)
{
    int i = size++;
    h[i] = s;
    hasit[s->key] = true;
    while(i > 0)
    {
        int j = (i - 1) >> 1;
        if(h[j]->f <= h[i]->f) break;
        Status *t = h[j];
        h[j] = h[i];
        h[i] = t;
        i = j;
    }
}

// 删除堆顶元素
Status *StatusHeap::delMax()
{
    Status *max = h[0];
    int i = 0, j;
    h[0] = h[--size];
    hasit[max->key] = false;
    while(i != (j = properParent(i)))
    {
        Status *t = h[j];
        h[j] = h[i];
        h[i] = t;
        i = j;
    }
    return max;
}

// 查重
bool StatusHeap::inHeap(int k)
{
    return hasit[k];
}

int main(int argc, char** argv)
{

        // 读入数据
        auto *cur = new Status(nullptr);
        char x;
        for(int i = 0; i < 9; ++i)
        {
            cin >> x;
            cur->matrix[i] = x - '0';
            if(x == '0') cur->pos0 = i;
        }
        cur->key = cur->calckey(); cur->calcf();

        // 新建堆，方便读取f最小值
        auto *open = new StatusHeap, *close = new StatusHeap;
        open->insert(cur);

        // 当OPEN表不为空
        while(open->Size() > 0)
        {
            // 取出最小值
            cur = open->delMax();

            // 如果OPEN堆顶是目标节点，则退出
            if(cur->h == 0)
            {
                cout << cur->g << endl;
                break;
            }

            // OPEN堆顶元素加入CLOSE
            close->insert(cur);

            // 向上下左右扩展节点，加入OPEN
            if(Status *a = cur->canGoL(open, close))
            {
                open->insert(a);
            }
            if(Status *a = cur->canGoR(open, close))
            {
                open->insert(a);
            }
            if(Status *a = cur->canGoU(open, close))
            {
                open->insert(a);
            }
            if(Status *a = cur->canGoD(open, close))
            {
                open->insert(a);
            }
        }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false)
#define what_is(x) cerr << #x << " is " << x << endl
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
struct matrix{
    int arr[3][3];
    bool operator < (const matrix other) const{
        rep(i, 0, 3)
            rep(j, 0, 3) {
                if (arr[i][j] < other.arr[i][j])
                    return true;
                if (arr[i][j] > other.arr[i][j])
                    return false;
            }
        return false;
    }
};
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
matrix a;
matrix b = {
    .arr = {
        {1,2,3},
        {8,0,4},
        {7,6,5}
    }
};
int main() {
    //freopen("test.in", "r", stdin);
    char tmp;
    rep(i, 0, 3)
        rep(j, 0, 3) {
            scanf("%c", &tmp);
            a.arr[i][j] = tmp - '0';
        }
    queue<matrix> q;
    q.push(a);
    map<matrix, int> s;
    s[a] = 0;
    while (q.size() && s.find(b) == s.end()) {
        matrix head = q.front();
        q.pop();
        rep(x, 0, 3)
            rep(y, 0, 3) {
                if (head.arr[x][y] != 0)
                    continue;
                rep(i, 0, 4) {
                    int xx = x+dx[i];
                    int yy = y+dy[i];
                    if (0 <= xx && xx < 3 && 0 <= yy && yy < 3 ) {
                        matrix p = head;
                        swap(p.arr[x][y], p.arr[xx][yy]);
                        if (s.find(p) == s.end()) {
                            q.push(p);
                            s[p] = s[head] + 1;
                        }
                    }
                }
            }
    }
    printf("%d\n", s[b]);


}

hash+双向bfs
对每一个状态都计算它对应的位置数（这里使用状态（9进制）对应的10进制数），使用求余的hash来存储它的位置

//2017/07/24 by:TBB000623/LJM000623
//8_num_question
//from Luogu1379/Vijos1360/CODEVS1225

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <cstdlib> 
using namespace std;
typedef unsigned u32;
queue<u32>  qu;
queue< pair<u32,int> >  requ;
vector< vector< pair<u32,int> > >   hash_step,rehash_step;

const u32 MOD=100019;
u32 calc(const vector<int> &in) {
    u32 S=0;
    for(int i=0;i<9;i++)    S=9*S+in[i];
    return S;
}
vector<int> recalc(int in)  {
    vector<int> S;
    S.resize(9);
    for(int i=8;i>=0;i--)   S[i]=in%9,in/=9;
    return S;
}
vector< pair<u32,int> >::iterator   ser(u32 ha_in)  {
    vector< pair<u32,int> >::iterator   iter;
    for(iter=hash_step[ha_in%MOD].begin();iter!=hash_step[ha_in%MOD].end();iter++)  if(iter->first==ha_in)  break;
//  if(iter==hash_step[ha_in%MOD].end())    cerr<<"A"<<ha_in<<endl;
    return iter;
}
vector< pair<u32,int> >::iterator   reser(u32 ha_in)    {
    vector< pair<u32,int> >::iterator   iter;
    for(iter=rehash_step[ha_in%MOD].begin();iter!=rehash_step[ha_in%MOD].end();iter++)  if(iter->first==ha_in)  break;
//  if(iter==hash_step[ha_in%MOD].end())    cerr<<"A"<<ha_in<<endl;
    return iter;
}
int zero(const vector<int> &in) {
    int i=0;
    while(in[i]!=0) i++;
    return i;
}

inline u32  calc_left(vector<int> in,int zero_pos)  {
    swap(in[zero_pos],in[zero_pos-1]);
    return calc(in);
}
inline u32  calc_up(vector<int> in,int zero_pos)    {
    swap(in[zero_pos],in[zero_pos-3]);
    return calc(in);
}
inline u32  calc_right(vector<int> in,int zero_pos) {
    swap(in[zero_pos],in[zero_pos+1]);
    return calc(in);
}
inline u32  calc_down(vector<int> in,int zero_pos)  {
    swap(in[zero_pos],in[zero_pos+3]);
    return calc(in);
}

void bfs(int lim)   {
    while(!qu.empty())  {
        u32 a=qu.front();           
        vector<int> ve=recalc(a);
        int zero_pos=zero(ve);
        vector< pair<u32,int> >::iterator   iter=ser(a);        
        int ste=iter->second;
        if(ste>lim) break;
        qu.pop();
        
        if(ste>=16) continue;
        
        if(zero_pos%3!=0)   {
            u32 k=calc_left(ve,zero_pos);
            iter=ser(k);
            if(iter==hash_step[k%MOD].end())    {
                hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                qu.push(k);
            }
        }
        if(zero_pos%3!=2)   {
            u32 k=calc_right(ve,zero_pos);
            iter=ser(k);
            if(iter==hash_step[k%MOD].end())    {
                hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                qu.push(k);
            }
        }
        if(zero_pos>=3) {
            u32 k=calc_up(ve,zero_pos);
            iter=ser(k);
            if(iter==hash_step[k%MOD].end())    {
                hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                qu.push(k);
            }
        }
        if(zero_pos<6)  {
            u32 k=calc_down(ve,zero_pos);
            iter=ser(k);
            if(iter==hash_step[k%MOD].end())    {
                hash_step[k%MOD].push_back(pair<u32,int>(k,ste+1));
                qu.push(k);
            }
        }
    }
}
void rebfs(int lim) {
    while(!requ.empty())    {
        pair<u32,int>   pa=requ.front();    
//      cout<<pa.first<<" "<<pa.second<<endl;
        vector< pair<u32,int> >::iterator   iter=ser(pa.first);
        if(iter!=hash_step[pa.first%MOD].end()) {
            cout<<iter->second+pa.second<<endl;
            exit(0);
        }
//      hash_step[pa.first%MOD].push_back(pa);
        vector<int> ve=recalc(pa.first);
        int zero_pos=zero(ve);
        
        if(pa.second>lim)   break;
        requ.pop();
        
        
        if(zero_pos%3!=0)   {
            u32 k=calc_left(ve,zero_pos);
            iter=reser(k);
            if(iter==rehash_step[k%MOD].end())  {
                rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                requ.push(pair<u32,int>(k,pa.second+1));
            }
        }
        if(zero_pos%3!=2)   {
            u32 k=calc_right(ve,zero_pos);
            iter=reser(k);
            if(iter==rehash_step[k%MOD].end())  {
                rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                requ.push(pair<u32,int>(k,pa.second+1));
            }
        }
        if(zero_pos>=3) {
            u32 k=calc_up(ve,zero_pos);
            iter=reser(k);
            if(iter==rehash_step[k%MOD].end())  {
                rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                requ.push(pair<u32,int>(k,pa.second+1));
            }
        }
        if(zero_pos<6)  {
            u32 k=calc_down(ve,zero_pos);
            iter=reser(k);
            if(iter==rehash_step[k%MOD].end())  {
                rehash_step[k%MOD].push_back(pair<u32,int>(k,-1));
                requ.push(pair<u32,int>(k,pa.second+1));
            }
        }
    }
}
int main()  {
    int be_pos[9]={1,2,3,8,0,4,7,6,5};
    int en_pos[9];
    char in[10];
    scanf("%s",in);
    hash_step.resize(MOD);
    rehash_step.resize(MOD);
    for(int i=0;i<9;i++)    en_pos[i]=in[i]-'0';
    vector<int> be_ve(&be_pos[0],&be_pos[9]);
    vector<int> en_ve(&en_pos[0],&en_pos[9]);
    int hash_be_ve=calc(be_ve);
    int hash_en_ve=calc(en_ve);
    hash_step[hash_be_ve%MOD].push_back(pair<u32,int>(hash_be_ve,0));
    qu.push(hash_be_ve);
    requ.push(pair<u32,int>(hash_en_ve,0));
    rehash_step[hash_en_ve%MOD].push_back(pair<u32,int>(hash_en_ve,0));
    
    int limts;
    for(limts=0;limts<100;limts++)  {
        bfs(limts);
        rebfs(limts);
    }
    cout<<"No solution!"<<endl;
    return 0;
}

#include<cstring>
#include <stdio.h>

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<stack>

#include<queue>
#include<list>
#include<cmath>
#include<string>
#include<map>
//#include<stdafx.h>
using namespace std;
struct node {
    int  x[3][3],step;

} in;
int en[3][3]= { { 1,2,3 },{ 8,0,4 },{ 7,6,5 } };
queue<node>p;
map <int, bool> ts;
bool l(node u) {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (u.x[i][j] != en[i][j])
                return false;
    return true;
}
int magicpro(node d) {
    int fin=0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            fin *= 10;
            fin += d.x[i][j];
        }
    return fin;
}

int main() {
    ios::sync_with_stdio(false);
    int y;
    cin >> y;
    for (int i = 2; i >=0; i--)
        for (int j =2; j >=0; j--){
            
            
            in.x[i][j] = y % 10;
            y /= 10;
        }
    in.step = 0;
    
    
    
    p.push(in);
    
    while (true) {
        int o, s;
        if (l(p.front()) == true)
        {
            cout << p.front().step;
            break;
        }
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (p.front().x[i][j] == 0)
                {
                    o = i;
                    s = j;
                }
        node ans = p.front();
        p.pop();
        ans.step++;
        if (ts[magicpro(ans)] == true)
            continue;
        else
            ts[magicpro(ans)] = true;
        if (s > 0)
        {
            swap(ans.x[o][s], ans.x[o][s - 1]);
            p.push(ans);
            swap(ans.x[o][s], ans.x[o][s - 1]);
        }
        if (s <2)
        {
            swap(ans.x[o][s], ans.x[o][s + 1]);
            p.push(ans);
            swap(ans.x[o][s], ans.x[o][s +1]);
        }
        if (o > 0)
        {
            swap(ans.x[o][s], ans.x[o-1][s]);
            p.push(ans);
            swap(ans.x[o][s], ans.x[o-1][s ]);
        }
        if (o<2)
        {
            swap(ans.x[o][s], ans.x[o+1][s ]);
            p.push(ans);
            swap(ans.x[o][s], ans.x[o+1][s ]);
        }
    }
    //system("pause");
    return 0;
}

这题实际上很水，就是BFS+哈希。但是一开始不太会写哈希，导致爆内存，直到知道了map这个好东西，直接秒掉了。（ps：为了方便乱写的变量民请无视……）

暴力bfs+判重

#include<iostream>
using namespace std;
int head,tail;
short f[10000000][9];
int step[10000000]={0},zero[10000000];
int ans=-1;
bool judge[87654321]={0};

bool done(short a[])
{
    int bit_8=0;
    for(int i=0;i<=7;i++)
    {
        bit_8*=10;
        bit_8+=a[i];
    }
    if(judge[bit_8]==0)
    {
        judge[bit_8]=1;
        return 0;
    }
    else
        return 1;
}

void start()
{
    int input;
    cin>>input;
    for(int i=0;i<9;i++)
    {
        f[1][8-i]=input % 10;
        input=input/10;
        if(f[1][8-i]==0)
            zero[1]=8-i;
    }
    if(f[1][0]==1&&f[1][1]==2&&f[1][2]==3
    &&f[1][3]==8&&f[1][4]==0&&f[1][5]==4
    &&f[1][6]==7&&f[1][7]==6&&f[1][8]==5)
    {ans=0;
    cout<<ans;
    }
}

void if_finished(short a[])
{
    int bit_8=0;
    for(int i=0;i<=8;i++)
    {
        bit_8*=10;
        bit_8+=a[i];
    }
    if(bit_8==123804765)
    {
        ans=step[head]+1;
        cout<<ans;
    }
}

void move(int type)
{
    if(ans!=-1)return;
    short mov[4]={-3,3,-1,1};
    short a[9];
    for(int i=0;i<9;i++)
        a[i]=f[head][i];
    a[zero[head]]=a[zero[head]+mov[type]];
    a[zero[head]+mov[type]]=0;
    if_finished(a);
    if(done(a)==0)
    {
        tail++;
        for(int i=0;i<9;i++)
        f[tail][i]=a[i];
        zero[tail]=zero[head]+mov[type];
        step[tail]=step[head]+1;
    }
}

int main()
{
    start();
    head=1;tail=1;
    while(ans==-1&&head<=tail)
    {
        if(zero[head]!=0&&zero[head]!=1&&zero[head]!=2)
            move(0);
        if(zero[head]!=6&&zero[head]!=7&&zero[head]!=8)
            move(1);
        if(zero[head]!=0&&zero[head]!=3&&zero[head]!=6)
            move(2);
        if(zero[head]!=2&&zero[head]!=5&&zero[head]!=8)
            move(3);
        head++;
    }
    if(ans==-1)
        cout<<-1;
    return 0;
}

BFS

#include <queue>
#include <algorithm>
#include <cstdio>
#include <map>
#include <iostream>
using namespace std;
int target_[3][3]={{1,2,3},{8,0,4},{7,6,5}};

struct Stat 
{
    int c[3][3];
    Stat(int _c[3][3])
    {
        for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            c[i][j] = _c[i][j];
        }
    }
    Stat(const Stat &other)
    {
        for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
        {
            c[i][j] = other.c[i][j];
        }
    }
    bool operator< (const Stat &other) const
    {
        for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
          {
            if (c[i][j] < other.c[i][j]) return true;
            if (c[i][j] > other.c[i][j]) return false;
          }
        return false;
    }
};

const Stat target(target_);

map <Stat,int> Map;
queue <Stat> que;
int main()
{
    
    Map.clear();
    int orig_[3][3];
    for(int i = 0; i < 3; i++)
    for (int j = 0; j< 3;j++)
        scanf("%1d",&orig_[i][j]);
    Stat orig(orig_);
    que.push(orig);
    Map[orig] = 0;
    while (que.size() && Map.find(target) == Map.end())
    {
        Stat s = que.front(); que.pop();
        int count = Map[s],blank_x=-1,blank_y=-1;
        for (int i = 0; i < 3 && blank_x == -1; i++)
        {
            for (int j = 0; j < 3; j++)
                if (s.c[i][j] == 0)
                {
                    blank_x = i;
                    blank_y = j;
                    break;
                }
        }
        int dx[4]={-1,1,0,0}, dy[4] = {0,0,1,-1};
        for (int i = 0; i < 4; i++)
        {
            int nx = blank_x + dx[i], ny = blank_y +dy[i];
            if (nx >=0 && nx < 3 && ny>=0 && ny<3)
            {
                Stat ns(s);
                ns.c[blank_x][blank_y] = ns.c[nx][ny];
                ns.c[nx][ny] = 0;
                if (Map.find(ns) == Map.end())
                {
                    que.push(ns);
                    Map[ns] = Map[s] + 1;
                }   
            }
        }   
    } 
    cout << Map[target] << endl;    
    
}

人生第一个启发式搜索……0ms，很强势
具体见注释：

#include <iostream>
#include <deque>
#include <algorithm>
#include <cstdlib>
#define _abs(x) (x>=0?x:-x)//绝对值函数
#define h_size 14233333//哈希表大小
#define hash(x) (x%h_size)
using namespace std;
typedef pair<int,int> pii;
const int _end=123804765,_enp[2][9]={{1,0,0,0,1,2,2,2,1},{1,0,1,2,2,2,1,0,0}};//end为目标状态,enp[0][i]表示目标状态中数字i所在的行,enp[1][i]表示数字i所在的列
int _sta;//开始状态
bool _clo[h_size];//a*算法的close表
deque<pii> _ol;//a*算法的open表
int h(int key)//估值函数，使用曼哈顿距离估值
{
    int _map[3][3],_kp[2][9],sum=0;
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--)_kp[0][key%10]=i,_kp[1][key%10]=j,key/=10;
    for(int i=0;i<9;i++)sum+=abs(_kp[0][i]-_enp[0][i])+abs(_kp[1][i]-_enp[1][i]);
    return sum;
}
int move(int key,char _ctr)//移动数字0函数,u表示向上，d表示向下,l表示向左,r表示向右
{
    int _kb=key,_map[3][3],i0,j0;
    for(int i=2;i>=0;i--)for(int j=2;j>=0;j--){_map[i][j]=_kb%10,_kb/=10;if(_map[i][j]==0)i0=i,j0=j;}
    switch(_ctr)//如果无法扩展（即到达边界）就返回移动前的值
    {
        case 'u':if(i0==0)return key;swap(_map[i0][j0],_map[i0-1][j0]);break;
        case 'd':if(i0==2)return key;swap(_map[i0][j0],_map[i0+1][j0]);break;
        case 'l':if(j0==0)return key;swap(_map[i0][j0],_map[i0][j0-1]);break;
        case 'r':if(j0==2)return key;swap(_map[i0][j0],_map[i0][j0+1]);break;
    }
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)_kb=_kb*10+_map[i][j];
    return _kb;
}
bool cmp(pii a,pii b){return a.second<b.second;}//二分查找比较函数
void work(pii _nex)//处理新状态
{
    if(_nex.first==_end)cout<<_nex.second-h(_nex.first),exit(0);//发现正解，直接输出并结束程序
    if(!_clo[hash(_nex.first)])_ol.insert(lower_bound(_ol.begin(),_ol.end(),_nex,cmp),_nex);//二分查找插入新状态
}
int main()
{
    cin>>_sta;
    _ol.push_back(make_pair(_sta,h(_sta)));//把开始状态加入到open表中
    while(!_ol.empty())//处理open表
    {
        pii _now=_ol.front();
        _ol.pop_front(),_clo[hash(_now.first)]=1;//把当前open表中的最优状态取出并加入到close表中
        int _nex=move(_now.first,'u');//扩展新状态
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'d');
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'l');
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1)),_nex=move(_now.first,'r');
        work(make_pair(_nex,_now.second-h(_now.first)+h(_nex)+1));
    }
    return 0;
}

纯广搜，暴力AC
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <map>
using namespace std;
struct que{
char m[3][3];
int step;
} q[1000000];
map <string,bool> vis;           //用map模仿hash 
int h=0,t=0;
char aim[3][3]={{'1','2','3'},{'8','0','4'},{'7','6','5'}};
int xx[4]={1,-1,0,0},yy[4]={0,0,-1,1};
char m[3][3];
string s;
bool judge(char a[][3],char b[][3]){    //判断是否与目标相同 
for(int i=0;i<3;i++)
 for(int j=0;j<3;j++)
   if(a[i][j]!=b[i][j])
     return false;
return true;
}
void insert(char a[][3],int step,string s){   //入队 
t++;
for(int i=0;i<3;i++)
 for(int j=0;j<3;j++)
   q[t].m[i][j]=a[i][j];
q[t].step=step;
vis[s]=true;                 //访问标记 
}
void take(char a[][3]){          //出队 
h++;
for(int i=0;i<3;i++)
 for(int j=0;j<3;j++)
   a[i][j]=q[h].m[i][j];
}
void work(char a[][3],int step){
int x,y;
for(int i=0;i<3;i++)
 for(int j=0;j<3;j++)
   if(a[i][j]=='0'){
 x=i,y=j;
 break;
}
for(int i=0;i<4;i++)
 if(x+xx[i]>=0 && y+yy[i]>=0 && x+xx[i]<3 && y+yy[i]<3){
  a[x][y]=a[x+xx[i]][y+yy[i]];
a[x+xx[i]][y+yy[i]]='0';
string s;                   //把矩阵转换成一个string来作为访问 
   for(int j=0;j<3;j++)
     for(int k=0;k<3;k++)
       s+=a[j][k];
if(vis[s]!=true)
 insert(a,step+1,s);
a[x+xx[i]][y+yy[i]]=a[x][y];
a[x][y]='0';
 }
}
int bfs(){
char k[3][3];
while(h<t){
 take(k);
 if(judge(k,aim))
  return q[h].step;
 work(k,q[h].step);
}
}
int main(){
int cnt=0;
cin>>s;
for(int i=0;i<3;i++)
 for(int j=0;j<3;j++)
   m[i][j]=s[cnt++];
insert(m,0,s);
vis[s]=true;
printf("%d\n",bfs());
return 0;
}

数据好弱啊...根本不用A*
暴力+康托展开就好了...
测试数据 #0: Accepted, time = 0 ms, mem = 9028 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 9028 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 9028 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 9028 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 9028 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 9032 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 9028 KiB, score = 20
测试数据 #7: Accepted, time = 31 ms, mem = 9028 KiB, score = 20
Accepted, time = 154 ms, mem = 9032 KiB, score = 100
pascal
program P1360;
const
p:array[0..9] of longint=(1,1,2,6,24,120,720,5040,40320,362880);
final:array[1..9] of shortint=(1,2,3,8,0,4,7,6,5);
type
arr=array[1..9] of shortint;
ty=record
map:arr;
depth,loc:longint;
end;
var
list:array[1..400000] of ty;
hash:array[0..400000] of boolean;
i,j,t,open,closed:longint;
start:arr;
function find(x:arr):boolean;
var
i:longint;
begin
for i:=1 to 9 do if x[i]<>final[i] then exit(false);
exit(true);
end;
function con(x:arr):longint; //康托展开
var
i,t:longint;
begin
con:=0;
for i:=1 to 9 do
begin
t:=x[i];
for j:=1 to i do if x[j]<x[i] then dec(t);
inc(con,t*p[9-i]);
end;
end;
procedure dfs(x:shortint);
var
t:arr;
temp:longint;
begin
t:=list[open].map;
t[list[open].loc]:=t[x];
t[x]:=0;
temp:=con(t);
if find(t) then
begin
writeln(list[open].depth+1);
halt;
end;
if not hash[temp] then
begin
list[closed].map:=t;
list[closed].depth:=list[open].depth+1;
list[closed].loc:=x;
hash[temp]:=true;
inc(closed);
end;
end;
begin
readln(t);
for i:=9 downto 1 do
begin
start[i]:=t mod 10;
if start[i]=0 then list[1].loc:=i;
t:=t div 10;
end;
list[1].map:=start;
list[1].depth:=0;
open:=1;closed:=2;
if find(start) then
begin
writeln(0);
halt;
end;
fillchar(hash,sizeof(hash),false);
hash[con(start)]:=true;
repeat
t:=list[open].loc;
if (t<>3) and (t<>6) and (t<>9) then dfs(t+1);
if (t<>1) and (t<>4) and (t<>7) then dfs(t-1);
if (t>3) then dfs(t-3);
if (t<7) then dfs(t+3);
inc(open);
until open=closed;
end.


'''c++
#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#define M 1000003
using namespace std;
const int goal[10]={0,1,2,3,8,0,4,7,6,5};
int ans;
struct Node{
int s[10],step;
};
Node hash[M];
int head[M],next[M];
int hash_size;

queue<Node> q;
int findzero(Node a){
int pos=1;
while(1)
{
if(a.s[pos]==0)
break;
pos++;
}

return pos;
}
bool check(Node x){
for(int i=1;i<=9;i++)
{
if(x.s[i]!=goal[i])
return false;
}
return true;
}
//hashÅÐÖØ
bool same(Node x,Node y){
for(int i=1;i<=9;i++)
{
if(x.s[i]!=y.s[i])
return false;
}
return true;
}
int create_hash(Node x){
int hashnum=0;
for(int i=1;i<=9;i++)
hashnum=hashnum*10+x.s[i];
return hashnum % M;

}
bool insert(Node x){
int h=create_hash(x);
int i=head[h];
while(i)
{
if(same(x,hash[i]))
return false;
i=next[i];
}
hash_size++;
next[hash_size]=head[h];
head[h]=hash_size;
hash[hash_size]=x;
return true;
}
int main(){
string start;
cin>>start;//¶ÁÈë
Node st;
st.step=0;
for(int i=0;i<9;i++)
st.s[i+1]=start[i]-'0';//×Ö·ûתÊý×Ö
insert(st);
q.push(st);//bfs
while(!q.empty()){
Node head=q.front();
q.pop();//³ö¶ÓÁÐ
if(check(head))
{
ans=head.step;
break;
}
//¼ì²é
Node move;
int pos=findzero(head);
if(pos>=3)
{
move=head;
int swappos=pos-3;
swap(move.s[pos],move.s[swappos]);
move.step++;
if(insert(move))
q.push(move);
}
//0ÏòÉÏ 1 2 3²»ÐÐ
if(pos<=6){
move=head;
int swappos=pos+3;
swap(move.s[pos],move.s[swappos]);
move.step++;
if(insert(move))
q.push(move);
}
//0ÏòÏ 7 8 9²»ÐÐ
if(pos % 3!=0){
move=head;
int swappos=pos+1;
swap(move.s[pos],move.s[swappos]);
move.step++;
if(insert(move))
q.push(move);
}
//0Ïò×ó 3 6 9ÎÞ·¨Ïò×ó
if(pos % 3!=1){
move=head;
int swappos=pos-1;
swap(move.s[pos],move.s[swappos]);
move.step++;

if(insert(move))
q.push(move);
}
//0ÏòÓÒ 1 4 7ÎÞ·¨ÏòÓÒ

}
printf("%d",ans);

return 0;
}
'''

link
AC50