网友投稿 622 2022-11-20
青蛙跳杯子
经典算法无需注解
#include#include#include#include#includeusing namespace std;string s1,s2;int ans = 0;map mp;struct Node{ string s; int step; Node(string s,int step):s(s),step(step){}};//跳跃后s 和步数void bfs(){ //创建队列 queue q; q.push(Node(s1,0));//放入第一个 while(!q.empty()) { Node node = q.front();//取出第一个 q.pop(); //将该对象删除 if(node.s==s2) //找到了 返回 { ans = node.step; return; } //没找到 int size = node.s.size(); for(int i = 0;i < size;i++)//遍历每一只青蛙 { for(int j = -3;j<=3;j++) //每一只青蛙可以怎么跳 { string temp = node.s; if(i+j<0||i+j>=size||temp[i+j]!='*') continue; //青蛙这里开始跳 swap(temp[i+j],temp[i]); if(!mp[temp]) { mp[temp] = 1; q.push(Node(temp,node.step+1)); } } } } }int main(){ cin >> s1 >> s2; bfs(); cout << ans << endl; return 0;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~