特别声明:紫书上抄来的代码,详见P198
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初试状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1：
283104765
输出样例#1：
4
判重一 //set
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>//测试
#include<algorithm>
using namespace std;
typedef int state[]; state st[],goal={,,,,,,,,};
int dis[],dx[]={-,,,},dy[]={,,-,}; set<int> vis;
void init_lookup_table(){vis.clear();}
int try_to_insert(int s){
int v=;
for(int i=;i<;i++)v=v*+st[s][i];
if(vis.count(v)) return ;
vis.insert(v);
return ;
} int bfs(){
init_lookup_table();
int front=,rear=;
while(front<rear){
state& s=st[front];
if(memcmp(goal,s,sizeof(s))==)return front; int z;
for(z=;z<;z++) if(!s[z]) break;
int x=z/,y=z%;
for(int d=;d<;d++){
int newx=x+dx[d];
int newy=y+dy[d];
int newz=newx*+newy;
if(newx>=&&newx<&&newy>=&&newy<){
state& t=st[rear];
memcpy(&t,&s,sizeof(s));//Copy
t[newz]=s[z];
t[z]=s[newz];
dis[rear]=dis[front]+;
if(try_to_insert(rear)) rear++;
}
}
front++;
}
return ;
} int main(){
// freopen("01.in","r",stdin);
string s;cin>>s;
for(int i=;i<=;i++)st[][i]=s[i]-''; int ans=bfs();
if(ans>) printf("%d\n",dis[ans]);
else printf("-1\n");
return ;
}紫书上说stl很慢,但是......
膜拜洛谷测评机
不过这是一个好方法吧.比如状态很多但很分散就可以类比set
判重二 //hash
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>//测试
#include<algorithm>
using namespace std;
typedef int state[]; state st[],goal={,,,,,,,,};
int dis[],dx[]={-,,,},dy[]={,,-,}; const int hashsize=;
int head[hashsize],next[hashsize];
void init_lookup_table(){memset(head,,sizeof(head));}
int hash(state& s){
int v=;
for(int i=;i<;i++) v=v*+s[i];
return v%;
}
int try_to_insert(int s){
int h=hash(st[s]);
int u=head[h];
while(u){
if(memcmp(st[u],st[s],sizeof(st[s]))== )return ;
u=next[u];
}
next[s]=head[h];
head[h]=s;
return ;
} int bfs(){
init_lookup_table();
int front=,rear=;
while(front<rear){
state& s=st[front];
if(memcmp(goal,s,sizeof(s))==)return front; int z;
for(z=;z<;z++) if(!s[z]) break;
int x=z/,y=z%;
for(int d=;d<;d++){
int newx=x+dx[d];
int newy=y+dy[d];
int newz=newx*+newy;
if(newx>=&&newx<&&newy>=&&newy<){
state& t=st[rear];
memcpy(&t,&s,sizeof(s));//Copy
t[newz]=s[z];
t[z]=s[newz];
dis[rear]=dis[front]+;
if(try_to_insert(rear)) rear++;
}
}
front++;
}
return ;
} int main(){
// freopen("01.in","r",stdin);
string s;cin>>s;
for(int i=;i<=;i++)st[][i]=s[i]-''; int ans=bfs();
if(ans>) printf("%d\n",dis[ans]);
else printf("-1\n");
return ;
}震惊!!!
判重三 //编码(只适用于码数很小的情况下,比如30!就不行)
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>//测试
#include<algorithm>
using namespace std;
typedef int state[]; state st[],goal={,,,,,,,,};
int dis[],dx[]={-,,,},dy[]={,,-,}; int vis[],fact[];
void init_lookup_table(){
fact[]=;
for(int i=;i<;i++) fact[i]=fact[i-]*i;
}
int try_to_insert(int s){
int code=;//把st[s]映射到整数code
for(int i=;i<;i++){
int cnt=;
for(int j=i+;j<;j++)if(st[s][j]<st[s][i]) cnt++;
code+=fact[-i]*cnt;
}
if(vis[code])return ;
return vis[code]=;
} int bfs(){
init_lookup_table();
int front=,rear=;
while(front<rear){
state& s=st[front];
if(memcmp(goal,s,sizeof(s))==)return front; int z;
for(z=;z<;z++) if(!s[z]) break;
int x=z/,y=z%;
for(int d=;d<;d++){
int newx=x+dx[d];
int newy=y+dy[d];
int newz=newx*+newy;
if(newx>=&&newx<&&newy>=&&newy<){
state& t=st[rear];
memcpy(&t,&s,sizeof(s));//Copy
t[newz]=s[z];
t[z]=s[newz];
dis[rear]=dis[front]+;
if(try_to_insert(rear)) rear++;
}
}
front++;
}
return ;
} int main(){
// freopen("01.in","r",stdin);
string s;cin>>s;
for(int i=;i<=;i++)st[][i]=s[i]-''; int ans=bfs();
if(ans>) printf("%d\n",dis[ans]);
else printf("-1\n");
return ;
}
总结起来就是:效率 hash>编码>set
另外这里有一个详细的转载：http://blog.csdn.net/ouxijv/article/details/7203027
