时间限制: 1 s 空间限制: 128000 KB 题目描述： Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们. 问题描述 在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。 输入描述： 输入初试状态，一行九个数字，空格用0表示 输出描述 ： 只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据) 样例输入 ： 283104765 样例输出 ： 4 这一道题其实也不是想象的那么难 代码如下
#include<cstdio>#include<cstdlib>#include<cstring>char a[4000000][10];int dj[1000000],bj1[100000],head=0,tail=1,jint pd1[9][9][9][9][9][9][9][9];//定义一个八维数组来判重 void bfs() { do { head++; for(int i=1; i<=4; i++) { j=bj1[head]+2*i-5; if(2*i-5==-1 &&(bj1[head]==3 || bj1[head]==6)) continue; if(2*i-5==1 &&(bj1[head]==2 || bj1[head]==5)) continue; if(j>=0&&j<9) { strcpy(a[++tail],a[head]); a[tail][bj1[head]]=a[tail][j]; a[tail][j]='0'; if(pd1[a[tail][0]-48][a[tail][1]-48][a[tail][2]-48][a[tail][3]-48][a[tail][4]-48][a[tail][5]-48][a[tail][6]-48][a[tail][7]-48]==0) {//判重 pd1[a[tail][0]-48][a[tail][1]-48][a[tail][2]-48][a[tail][3]-48][a[tail][4]-48][a[tail][5]-48][a[tail][6]-48][a[tail][7]-48]=1; dj[tail]=dj[head]+1; //步数+1 bj1[tail]=j; } else tail--; if(!strcmp(a[tail],"123804765")) { //判断是否满足条件 PRintf("%d",dj[tail]); //输出 exit(0); //退出 } } } } while(head<tail);}int main() { gets(a[1]); for(int jji=0; jji<9; jji++) { if(a[1][jji]=='0') { bj1[1]=jji; bfs(); } } return 0； }新闻热点
疑难解答
