算法也太难了吧

用户名：17306366773

访问量：11438

签　名：

我口袋只剩玫瑰一片，此行又山高路远

等　　级
排　　名	418
经　　验	4794
参赛次数	0
文章发表	41
年　　龄	0
在职情况	学生
学　　校	天津工业大学
专　　业

　　自我简介：

TA的其他文章

修剪灌木（C++）
浏览：509

X进制减法(C++)
浏览：1238

积木画（c++）
浏览：1093

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

常规bfs-青蛙跳杯子

　　作者: 算法也太难了吧　　　　发表时间：2022-02-11 16:21:27 浏览：101　|　评论：0　

原题链接：蓝桥杯2017年第八届真题-青蛙跳杯子

```cpp
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
string a,b;
int dis[]={1,-1,2,-2,3,-3};
struct node{
  string s;
  int c,p;
};
map<string,int> m;
void bfs(){
  int pos=a.find('*');
  queue<node> q;
  q.push({a,0,pos});
  m[a]=1;
  while(!q.empty()){
    node n=q.front();
    if(n.s==b){
      cout<<n.c;
      return;
    }
    q.pop();
    for(int i=0;i<6;i++){
      int tp=n.p+dis[i];
      if(tp<0||tp>=a.size()){
        continue;
      }
      string ts=n.s;
      swap(ts[n.p],ts[tp]);
      if(m[ts]){
        continue;
      }
      m[ts]=1;
      q.push({ts,n.c+1,tp});
    }
  }
}
int main()
{
  cin>>a>>b;
  bfs();
  return 0;
}
``````cpp
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
string a,b;
int dis[]={1,-1,2,-2,3,-3};
struct node{
  string s;
  int c,p;
};
map<string,int> m;
void bfs(){
  int pos=a.find('*');
  queue<node> q;
  q.push({a,0,pos});
  m[a]=1;
  while(!q.empty()){
    node n=q.front();
    if(n.s==b){
      cout<<n.c;
      return;
    }
    q.pop();
    for(int i=0;i<6;i++){
      int tp=n.p+dis[i];
      if(tp<0||tp>=a.size()){
        continue;
      }
      string ts=n.s;
      swap(ts[n.p],ts[tp]);
      if(m[ts]){
        continue;
      }
      m[ts]=1;
      q.push({ts,n.c+1,tp});
    }
  }
}
int main()
{
  cin>>a>>b;
  bfs();
  return 0;
}
```

0.0分

1 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

算法也太难了吧

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

常规bfs-青蛙跳杯子

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

简单的a+b （C语言代码）

【矩阵】（C++代码）

Tom数（C语言代码）

陈教主的三角形（C语言代码）

整除问题（C语言代码）

10月月赛题解

马拦过河卒（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

算法也太难了吧

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

常规bfs-青蛙跳杯子

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

简单的a+b （C语言代码）

【矩阵】 （C++代码）

Tom数 （C语言代码）

陈教主的三角形 （C语言代码）

整除问题 （C语言代码）

10月月赛题解

马拦过河卒 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

【矩阵】（C++代码）

Tom数（C语言代码）

陈教主的三角形（C语言代码）

整除问题（C语言代码）

马拦过河卒（C语言代码）