# 120 条题解

• @ 2018-03-13 21:47:15

启发式搜索+康拓展开

``````#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;
}
``````
• @ 2020-12-02 14:58:54

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

``````
#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) {
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;
}
}

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;
int tmp_array[9] = {0};
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;
if (queue[tail][0] == goalLong) {
printf("%ld", queue[tail][1]);
return 0;
}
tail++;
}

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

``````
• @ 2020-07-22 17:14:31

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;
}
``````
• @ 2017-12-16 23:11:06

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;
}

``````
• @ 2019-02-11 18:23:17

第一次一次性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;
}

``````
• @ 2019-01-10 11:34:18

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

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

struct node{
short a[10];//状态
short zero;//零点位置
short fore; //上一步的操作
short step; //搜索树层数（操作了多少步）
node *next;
};
//题目中给出的移动方式，可以等效于零点向四个方向移动
//x:1上；2，下；3，左；4，右
void move(node *head, node *tail, short x)
{
int k,i;
for(i=1;i<=9;i++)
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;
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，找到则返回该节点经历了多少步搜索。
{
node2 *p,*q;
short step;
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()
{
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; //用于记录步数，过渡用变量

//初始情况，存入宽搜队列
for(i=1;i<=9;i++)
{
scanf("%c",&ch);
k=(short) (ch-'0');
}
//初始情况加入查找树
hash1=new node2;
hash1->left=NULL;
hash1->right=NULL;
hash1->a=l;
//目标节点存入宽搜队列
for(i=1;i<=9;i++)
//目标节点加入查找树
hash2=new node2;
hash2->left=NULL;
hash2->right=NULL;
hash2->a=l;
//先操作初始队列，后操作返回队列，最后判断是否相遇
while(b==0)
{
//从前向后搜索
for(i=1;i<=4;i++)
if((i!=k)&&(movable(j,i)==1))//可以移动
{
p=new node;
l=hash(p);
step=p->step;
if(search_insert(l,hash1,step)==1)
delete p;
else {
tail1->next=p;
tail1=p;
p->next=NULL;
}

}
//释放刚刚拓展过的节点
delete p;

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

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

if((i!=k)&&(movable(j,i)==1))
{
p=new node;
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;
}

}

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

• @ 2018-12-01 21:41:20
``````#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;
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);
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++) {
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);
}
``````
• @ 2018-09-19 19:12:37

方法一：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;
}

``````
• @ 2018-05-02 21:17:04

#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;
}
{
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')
{
{
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]);
}
{
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]);
}
{
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]);
}
{
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;
}

• @ 2017-09-11 00:31:59

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

``````#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;
}

``````
• @ 2017-09-09 16:16:22
``````#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()) {
q.pop();
rep(x, 0, 3)
rep(y, 0, 3) {
continue;
rep(i, 0, 4) {
int xx = x+dx[i];
int yy = y+dy[i];
if (0 <= xx && xx < 3 && 0 <= yy && yy < 3 ) {
swap(p.arr[x][y], p.arr[xx][yy]);
if (s.find(p) == s.end()) {
q.push(p);
}
}
}
}
}
printf("%d\n", s[b]);

}

``````
• @ 2017-07-25 00:17:54

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;
}
``````
• @ 2017-07-08 17:04:13
``````#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：为了方便乱写的变量民请无视……）

• @ 2017-07-08 14:07:10

暴力bfs+判重

``````#include<iostream>
using namespace std;
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)
{
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++)
if_finished(a);
if(done(a)==0)
{
tail++;
for(int i=0;i<9;i++)
f[tail][i]=a[i];
}
}

int main()
{
start();
{
move(0);
move(1);
move(2);
move(3);
}
if(ans==-1)
cout<<-1;
return 0;
}
``````
• @ 2017-04-07 16:41:42

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;

}
``````
• @ 2017-01-19 13:59:32

人生第一个启发式搜索……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;
}
``````
• @ 2016-11-20 21:16:39

纯广搜，暴力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;
}

• @ 2016-11-13 21:21:43

数据好弱啊...根本不用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. ```

• @ 2016-07-30 20:44:17

'''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 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);
while(i)
{
if(same(x,hash[i]))
return false;
i=next[i];
}
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()){
q.pop();//³ö¶ÓÁÐ
{
break;
}
//¼ì²é
Node move;
if(pos>=3)
{
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){
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){
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){
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;
}
'''

• @ 2016-07-23 17:56:13

AC50

ID
1360

6

(无)

3851

922

24%

8