7.青蛙跳杯子 - 蓝桥云课
这个题目最后是抽象为bfs算法去解决的，一开始我怎么都没想到为什么会用bfs，后来看到他们的讲解才明白可以用bfs解决
任何可以用 BFS 解决的问题，都需要有以下几个要素：
状态（State）：问题的某个特定情况
初始状态（Start State）：问题的起始点
目标状态（Goal State）：想要达到的终点
状态转移（State Transition）：从一个状态到另一个状态的操作
状态空间（State Space）：所有可能状态的集合
青蛙跳杯子问题
↓ 抽象
"状态" = 杯子排列
"移动" = 合法交换
↓ 转化
图论问题：找从起点到终点的最短路径
↓ 实现
BFS：队列 + 状态记录 + 合法性检查
接下来就是代码实现了（典型的bfs模板）
#include<iostream> #include<algorithm> #include<cstring> #include<queue> #include<map> using namespace std; string s1,s2; int n; int d[6]={-3,-2,-1,1,2,3};//6个可能跳跃的方向 map<string,int> ans;//记录每个状态需要的步数 int bfs() { queue<string> q; q.push(s1); ans[s1]=0;//初始状态步数为0 while(q.size()) { string s=q.front(); q.pop(); int cnt=ans[s];//当前步数 int x=s.find('*');//找到空位置 for(int i=0;i<6;i++) { int z=x+d[i];//目标青蛙的位置 if(z>=0&&z<n) { swap(s[x],s[z]);//交换空杯与青蛙 //新状态没有被访问过 if(!ans.count(s)) { ans[s]=cnt+1;//记录步数 if(s==s2)return ans[s]; q.push(s); } swap(s[x],s[z]); } } } return -1; } int main() { cin>>s1>>s2; n=s1.length(); cout<<bfs(); return 0; }
