luoguP1379八数码难题（双向bfs）

作者：书琳天使_984 | 来源：互联网 | 2023-10-10 11:50

题目链接：https:www.luogu.orgproblemnewshowP1379题意：用字符串表示八数码，求根据给定八数码得到末状态

题目链接&＃xff1a;https://www.luogu.org/problemnew/show/P1379

题意&＃xff1a;用字符串表示八数码&＃xff0c;求根据给定八数码得到末状态“123804765”最少的步数。

思路&＃xff1a;这题很方便用双向bfs来优化&＃xff0c;用两个队列分别从起点、终点开始搜索&＃xff0c;两个map来记录该状态的步数。要注意的是起始状态和末状态相等的情况&＃xff0c;需要特判。

AC代码&＃xff1a;

#include
#include
#include
#include<string>
#include
#include
using namespace std;struct node{string s;int step,w;
};int go[4]&＃61;{-1,1,-3,3};
queue q1,q2;
map<string,int> mp1,mp2;bool isOK(int w,int k){int x&＃61;w&＃43;go[k];if(x<0||x>8) return false;if(w%3&＃61;&＃61;0&&k&＃61;&＃61;0) return false;if(w%3&＃61;&＃61;2&&k&＃61;&＃61;1) return false;return true;
}void bfs(){while(!q1.empty()&&!q2.empty()){node now1&＃61;q1.front();q1.pop();string s1&＃61;now1.s;int step1&＃61;now1.step,w1&＃61;now1.w;for(int i&＃61;0;i<4;&＃43;&＃43;i){if(!isOK(w1,i)) continue;int ww&＃61;w1&＃43;go[i],st&＃61;step1&＃43;1;string ss&＃61;s1;swap(ss[w1],ss[ww]);if(mp1[ss]) continue;if(mp2[ss]){printf("%d\n",step1&＃43;mp2[ss]-1);return;}mp1[ss]&＃61;st;node tmp&＃61;{ss,st,ww};q1.push(tmp);}node now2&＃61;q2.front();q2.pop();string s2&＃61;now2.s;int step2&＃61;now2.step,w2&＃61;now2.w;for(int i&＃61;0;i<4;&＃43;&＃43;i){if(!isOK(w2,i)) continue;int ww&＃61;w2&＃43;go[i],st&＃61;step2&＃43;1;string ss&＃61;s2;swap(ss[w2],ss[ww]);if(mp2[ss]) continue;if(mp1[ss]){printf("%d\n",step2&＃43;mp1[ss]-1);return;}mp2[ss]&＃61;st;node tmp&＃61;{ss,st,ww};q2.push(tmp);}}
}int main(){string s;cin>>s;if(s&＃61;&＃61;"123804765"){printf("0\n");return 0;}int w;for(int i&＃61;0;ii)if(s[i]&＃61;&＃61;&＃39;0&＃39;){w&＃61;i;break;}node bg&＃61;{s,1,w};node ed&＃61;{"123804765",1,4};mp1[s]&＃61;1,mp2["123804765"]&＃61;1;q1.push(bg),q2.push(ed);bfs();return 0;
}

转:https://www.cnblogs.com/FrankChen831X/p/11203514.html

推荐阅读

go
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
string
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
process
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
go
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
string
油田地块的划分和计数方法

本文介绍了一种划分和计数油田地块的方法。根据给定的条件，通过遍历和DFS算法，将符合条件的地块标记为不符合条件的地块，并进行计数。同时，还介绍了如何判断点是否在给定范围内的方法。 ... [详细]

蜡笔小新 2023-12-14 09:18:20
string
P1651 塔 (动态规划) 的最大高度计算方法

本文介绍了P1651题目的描述和要求，以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术，将问题转化为求解差值的问题，并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]

蜡笔小新 2023-12-13 19:52:19
tree
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
string
UVALive6575 Odd and Even Zeroes 数位dp+找规律

本文介绍了UVALive6575题目Odd and Even Zeroes的解法，使用了数位dp和找规律的方法。阶乘的定义和性质被介绍，并给出了一些例子。其中，部分阶乘的尾零个数为奇数，部分为偶数。 ... [详细]

蜡笔小新 2023-12-13 14:19:28
string
Codeforces 1294A题解：Collecting Coins整除+不整除问题解析

本文为Codeforces 1294A题目的解析，主要讨论了Collecting Coins整除+不整除问题。文章详细介绍了题目的背景和要求，并给出了解题思路和代码实现。同时提供了在线测评地址和相关参考链接。 ... [详细]

蜡笔小新 2023-12-14 21:14:58
format
向QTextEdit拖放文件的方法及实现步骤

本文介绍了在使用QTextEdit时如何实现拖放文件的功能，包括相关的方法和实现步骤。通过重写dragEnterEvent和dropEvent函数，并结合QMimeData和QUrl等类，可以轻松实现向QTextEdit拖放文件的功能。详细的代码实现和说明可以参考本文提供的示例代码。 ... [详细]

蜡笔小新 2023-12-14 16:06:38
format
C++省略号类型和参数个数不确定函数参数范例

本文介绍了C++中省略号类型和参数个数不确定函数参数的使用方法，并提供了一个范例。通过宏定义的方式，可以方便地处理不定参数的情况。文章中给出了具体的代码实现，并对代码进行了解释和说明。这对于需要处理不定参数的情况的程序员来说，是一个很有用的参考资料。 ... [详细]

蜡笔小新 2023-12-14 12:36:28
string
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
go
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
go
[CF949D]Curfew 二分答案是个不错的开头，困难部分在于如何检查

本文介绍了一个题目的解法，通过二分答案来解决问题，但困难在于如何进行检查。文章提供了一种逃逸方式，通过移动最慢的宿管来锁门时跑到更居中的位置，从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况，并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后，文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]

蜡笔小新 2023-12-13 09:08:55
go
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02

书琳天使_984

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章