洛谷 1379 八数码难题

题目描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入输出格式

输入格式：

输入初始状态，一行九个数字，空格用0表示

输出格式：

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入输出样例

输入样例1：  283104765 输出样例1： 4


Solution
　　首先每次挪动棋子，最多把一个棋子归位，所以当有N个棋子没有归位时，最少的步数是N，
只要当前步数加上N大于最优解，就可以证明肯定不是最优解，也就不需要继续搜索了。
// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std; const int dx[5]={1,0,-1,0}; const int dy[5]={0,1,0,-1}; const int p[10]={5,1,2,3,6,9,8,7,4}; int s,flag,r[10],a[5][5],_map[5][5],dis[10][10]; bool check() {for(int i=1;i<=9;i++)if(r[i]!=p[i])return 0;return 1; } int get() //A*剪枝 {int t=0;for(int i=1;i<=9;i++)t+=dis[r[i]][p[i]];return t; } int jue(int a,int b) {int t=a-b; return abs(t); } int calx(int i) {return (i-1)/3+1; } int caly(int i) {return i%3==0?3:i%3; } void dfs(int depth,int x,int y) {if(depth+get()>s) return; //剪枝if(check()) {flag=1; return;}//裸的暴搜for(int i=0;i<4;i++){int xx=x+dx[i],yy=y+dy[i];if(xx<1||yy<1||xx>3||yy>3) continue;swap(a[x][y],a[xx][yy]);swap(r[a[x][y]],r[a[xx][yy]]);dfs(depth+1,xx,yy);swap(a[x][y],a[xx][yy]);swap(r[a[x][y]],r[a[xx][yy]]);} } void pre() {for(int i=1;i<=9;i++)for(int j=i+1;j<=9;j++)dis[i][j]=dis[j][i]=calx(j)-calx(i)+jue(caly(i),caly(j)); } int main() {pre();int sx,sy;for(int i=1;i<=9;i++){char ch=getchar();int x=calx(i),y=caly(i);_map[x][y]=ch-'0'; r[ch-'0']=i;if(ch=='0') sx=x,sy=y;}for(s=0;;s++) {memcpy(a,_map,sizeof(_map)); dfs(0,sx,sy); if(flag) {printf("%d\n",s);break;}}return 0; }

 

转载于:https://www.cnblogs.com/Le-mon/p/8589751.html

总结

以上是生活随笔为你收集整理的洛谷 1379 八数码难题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。