首页 > 代码库 > codevs1225八数码难题（搜索·）
codevs1225八数码难题（搜索·）
1225 八数码难题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入描述 Input Description
输入初试状态，一行九个数字，空格用0表示
输出描述 Output Description
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入 Sample Input
283104765
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
详见试题
bfs
#include<iostream>#include<cstdio>#define N 500000using namespace std;struct node{ int mp[4][4];}a[N];int g[4][4]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};int xx[4] = {0,0,1,-1};int yy[4] = {1,-1,0,0};int hash[3733800];int step[N];int h,t=1,flag;int check(){ for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) if (a[t].mp[i][j] != g[i][j]) return 0; return 1;}int Hash(){ int s = 0,k = 1; for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) s += a[t].mp[i][j]*k,k*=7; s %= 3733799; if (!hash[s]) {hash[s] = 1;return 1;} return 0;}int pd(int x,int y){ if (x && x<=3 && y && y<=3) return 1; return 0;}void move(int x,int y){ for (int i=0;i<4;i++) { int p = x+xx[i], q = y+yy[i]; if (pd(p,q)) { for (int j=1;j<=3;j++) for (int k=1;k<=3;k++) a[t].mp[j][k] = a[h].mp[j][k]; swap(a[t].mp[x][y],a[t].mp[p][q]); step[t] = step[h] +1; if (check()) {cout<<step[t]; flag = 1;return;} if (Hash()) t++; } }}void search(){ while (h<t) { for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) { if (a[h].mp[i][j] == 0) move(i,j); if (flag) return; } h++; }}int main(){ string str; cin>>str; for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) a[0].mp[i][j] = str[(i-1)*3+j-1]-‘0‘; search();}
dfs
#include<bits/stdc++.h>using namespace std; int matrix[4][4]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};int dx[]={0,1,0,-1};int dy[]={1,0,-1,0};int st[4][4],dep,step;bool flag=false;int check(){ for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(st[i][j]!=matrix[i][j])return false; return true;}int jdg(int sx,int sy,int x,int y){ if(sx==x&&sy==y)return false; if(sx>0&&sy>0) if(sx<=3&&sy<=3) return true; return false;}void search(int x,int y,int fx,int fy){ if(check()){flag=true;return ;} if(step==dep)return ; for(int i=0;i<=3;i++) { int sx=x+dx[i]; int sy=y+dy[i]; if(jdg(sx,sy,fx,fy)) { swap(st[x][y],st[sx][sy]); step++; search(sx,sy,x,y); step--; swap(st[x][y],st[sx][sy]); } }}int main(){ int si,sj; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) { scanf("%c",&st[i][j]); st[i][j]-=‘0‘; if(st[i][j]==0)si=i,sj=j; } for(dep=0;;dep++) { search(si,sj,0,0); if(flag) { cout<<dep;return 0; } } return 0;}
codevs1225八数码难题（搜索·）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。