首页 > 其他分享 >Poj 3278 Catch That Cow (BFS+队列)

Poj 3278 Catch That Cow (BFS+队列)

时间:2024-02-02 19:23:29浏览次数:37  
标签:loc Cow int BFS start Poj line include

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,k,line[N],way;
struct node{int loc,step;};
queue<node> q;
void BFS(int n,int k){
    while(!q.empty()) q.pop();
    node start,next;
    start.loc=n;
    start.step=0;
    q.push(start);
    line[start.loc]=1;
    while(!q.empty()){
        start=q.front();
        q.pop();
        if(start.loc==k){
            cout<<start.step<<endl;
            break;
        }
        way=start.loc*2;
        if(way<=100000&&!line[way]){
            next.loc=way;
            line[way]=1;
            next.step=start.step+1;
            q.push(next);
        }
        way=start.loc+1;
        if(way<=100000&&!line[way]){
            next.loc=way;
            line[way]=1;
            next.step=start.step+1;
            q.push(next);
        }
        way=start.loc-1;
        if(way<=100000&&!line[way]){
            next.loc=way;
            line[way]=1;
            next.step=start.step+1;
            q.push(next);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(cin>>n>>k){
        memset(line,0,sizeof(line));
        BFS(n,k);
    }
    return 0;
}

 

标签:loc,Cow,int,BFS,start,Poj,line,include
From: https://www.cnblogs.com/accbulb/p/18003714

相关文章

  • Poj3126 Prime Path (BFS+筛素数)
    #include<iostream>#include<queue>#include<cstring>constintN=10010;intt,aa,bb,prime[N],vis[N],step[N];usingnamespacestd;voidprime_(){//埃式筛法prime[0]=prime[1]=1;for(inti=2;i<10000;i++){if(prime[i])contin......
  • POJ--2139 Six Degrees of Cowvin Bacon(最短路)
    记录20:342024-2-1http://poj.org/problem?id=2139最短路问题,使用Floyd后遍历选择就可以了。注意是多case输入,答案截尾。#include<cstdio>#include<cstring>#include<iostream>#defineMAX_N305#defineMAX_M10005usingnamespacestd;constintINF=0x3f3f3f3f;......
  • P2870 [USACO07DEC] Best Cow Line G
    https://www.luogu.com.cn/problem/P2870字典序最小显然贪心,若当前串首比串尾小,则取串首;若当前串首比串尾大,则取串尾。那串首串尾一样呢?这个顺序显然会影响到后续操作。考虑继续往内递归,如果碰到一样的,那么当前取什么都无所谓;若碰到不一样的,我们肯定是要取更小的那一边,因为这样......
  • POJ1182 食物链 (并查集的应用)
    POJ1182食物链(并查集的应用)Description动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述:第一种说法......
  • POJ2492 (并查集)
    POJ2492(并查集)题目:假设昆虫之间是异性互动,给出昆虫的互动情况,判断假设是否成立;输入:第一行t表示n个测试用例,每个测试用例第一行n,m表示n只昆虫,从1连续编号,m组互动情况;输出:假设不成立:Suspiciousbugsfound!假设成立:Nosuspiciousbugsfound!题解:参考POJ1611#include<cstdio......
  • POJ1611 (简单并查集)
    POJ1611(简单并查集)描述严重急性呼吸系统综合症(SARS)是一种病因不明的非典型肺炎,于2003年3月中旬被确认为全球性威胁。为了尽量减少传染给他人,最好的策略是将嫌疑人与其他人分开。在不传播你的疾病大学(NSYSU),有很多学生团体。同一小组中的学生相互交流频繁,一个学生可能会......
  • POJ 2524 (简单并查集)
    POJ2524(简单并查集)描述当今世界上有如此多不同的宗教,很难将它们全部记录下来。您有兴趣了解您所在大学的学生信仰多少种不同的宗教。您知道您的大学有n名学生(0<n<=50000)。你不可能询问每个学生的宗教信仰。此外,许多学生不愿意表达自己的信仰。避免这些问题的一种方......
  • 状压+BFS
    洛谷2622思路定义一个结构体节点,分别存储状态和步骤,状态的某一位是1表示灯开着,是0则表示该灯关,当状态为0000时输出的步骤即为最小步骤。点击查看代码#include<bits/stdc++.h>usingnamespacestd;//#defineintlonglong#definelllonglonginta[120][102]={0};int......
  • 洛谷题解-P2888 [USACO07NOV] Cow Hurdles S (Floyd)
    https://www.luogu.com.cn/problem/P2888题目描述FarmerJohnwantsthecowstoprepareforthecountyjumpingcompetition,soBessieandthegangarepracticingjumpingoverhurdles.Theyaregettingtired,though,sotheywanttobeabletouseaslittleene......
  • leetcode--98. 验证二叉搜索树(bfs)
    记录13:502024-1-28https://leetcode.cn/problems/validate-binary-search-tree/想岔方向了,想的太复杂了。首先思路是每个root节点必须大于左子树的最大节点,小于右边子树的最小节点。我的做法是记录下叶子节点,因为左边叶子节点的集合(vector)的最后一个节点为左子树的最大值......