首页 > 代码库 > 洛谷【P1379】八数码难题
洛谷【P1379】八数码难题
P1379 八数码难题
题目描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入输出格式
输入格式：
输入初试状态，一行九个数字，空格用0表示
输出格式：
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
输入输出样例
输入样例#1：
283104765
输出样例#1：
4
A*水之
喜闻乐见的Code
#include<cstdio>#include<algorithm>using namespace std;const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};const int aimx[10]={1,0,0,0,1,2,2,2,1};const int aimy[10]={1,0,1,2,2,2,1,0,0};int sta[3][3],Step,px,py,nowx[10],nowy[10];bool flag;int Guess() { int sum=0; for(int i=0;i<3;i++) for(int j=0;j<3;j++) nowx[sta[i][j]]=i,nowy[sta[i][j]]=j; for(int i=1;i<9;i++) sum+=(abs(aimx[i]-nowx[i])+abs(aimy[i]-nowy[i])); return sum;}void Astar(int nowstep,int Step,int px,int py) { if(flag||nowstep>Step) return; int H=Guess(); if(H==0) {flag=true;return;} if(H+nowstep>Step) return; for(int i=0;i<4;i++) { int x=px+dx[i],y=py+dy[i]; if(x<0||y<0||x>2||y>2) continue; swap(sta[x][y],sta[px][py]); Astar(nowstep+1,Step,x,y); swap(sta[x][y],sta[px][py]); } return;}int main() { for(int i=0;i<3;i++) for(int j=0;j<3;j++) { char c; scanf("%c",&c); sta[i][j]=c-‘0‘; if(sta[i][j]==0) px=i,py=j; } while(!flag) Step++,Astar(0,Step,px,py); printf("%d",Step); return 0;}
洛谷【P1379】八数码难题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。