109徐守佳

用户名：dotcpp0787174

访问量：1107

签　名：

想AC的我戴上了WA面具

等　　级
排　　名	878
经　　验	3559
参赛次数	3
文章发表	30
年　　龄	20
在职情况	学生
学　　校	内江师范学院
专　　业	虹夏虹夏虹

　　自我简介：

TA的其他文章

[CSP-J2020] 优秀的拆分--DFS+剪枝
浏览：45

[信息学奥赛一本通T1549-最大数] 线段树--单点修改区间查询
浏览：25

[信息学奥赛一本通T1547-区间和]-线段树做法
浏览：23

你可能喜欢

抓住那头牛! 双向BFS

　　作者: 109徐守佳　　　　发表时间：2024-09-12 13:06:48 浏览：34　|　评论：1　

原题链接：抓住那头牛

# 双向BFS
###### 更小的时间复杂度，更少的栈空间，更多的代码
###### tip：小题大做
``````cpp
#include<bits/stdc++.h>
#define ULL unsigned long long
#define LL long long
#define PII pair<int,int>
using namespace std;
const int N = 3 * 1e6 + 10,M = 2 * 1e3 + 10,inf = 0x3f3f3f3f;

int st,ed;
int extend(queue<int> &q,unordered_map<int,int> &da,unordered_map<int,int> &db,double d[])
{
    int t = q.front();
    q.pop();
    for(int i=0;i<3;i++)
    {
        if(d[i]==0.5 && t & 1) continue; 
        //special judge：奇数只能由加一或者减一得来，如果是奇数就不能除2
        int n;
        if(i==2) n = t * d[i];
        else n = t + d[i];
        if(da.count(n)) continue; //如果有已出现过的状态叉出去
        if(db.count(n))return da[t] + 1 + db[n]; 
        //如果找到两个状态相遇，返回两个状态记录步数之和+1
        da[n] = da[t] + 1; //记录下一个状态的步数
        q.push(n);
    }
    return -1; //没找到返回-1
}
int two_way_bfs()
{
    double da[3] = {1,-1,2},db[3] = {1,-1,0.5}; //da向前，db向后
    unordered_map<int,int> dista,distb; //记录状态和步数
    dista[st] = 0,distb[ed] = 0; //初始状态步数为0
    queue<int> qa,qb;
    qa.push(st);qb.push(ed);
    while (qa.size()&&qb.size())
    {
        int t;
        // 优先搜索状态少的队列，节约空间
        if(qa.size()<=qb.size()) t = extend(qa,dista,distb,da);
        else t = extend(qb,distb,dista,db);
        if(t!=-1) return t;
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>st>>ed;
    cout<<two_way_bfs();
    return 0;
}
```

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

yxy

%%% orz 蒟佬

2024-09-12 13:14:20

109徐守佳

TA的其他文章

你可能喜欢

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

【数组的距离】（C语言代码）

C二级辅导-分段函数（C语言代码）

分糖果（C++代码）

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

抓住那头牛! 双向BFS

评论区

精彩推荐

1011题解

剪刀石头布（C++代码）

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

C二级辅导-计负均正（C语言代码）

剪刀石头布（C语言代码）

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

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

小O的乘积（C语言代码）

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

A+B for Input-Output Practice (I) （C语言代码）

109徐守佳

TA的其他文章

你可能喜欢

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

【数组的距离】 （C语言代码）

C二级辅导-分段函数 （C语言代码）

分糖果 （C++代码）

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

抓住那头牛! 双向BFS

评论区

精彩推荐

1011题解

剪刀石头布 （C++代码）

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

C二级辅导-计负均正 （C语言代码）

剪刀石头布 （C语言代码）

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

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

小O的乘积 （C语言代码）

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

A+B for Input-Output Practice (I) （C语言代码）

【数组的距离】（C语言代码）

C二级辅导-分段函数（C语言代码）

分糖果（C++代码）

　　评论区

剪刀石头布（C++代码）

C二级辅导-计负均正（C语言代码）

剪刀石头布（C语言代码）

小O的乘积（C语言代码）