来源:http://poj.org/problem?id=3278
题意:给一个开始点和一个结束点,求从开始点到结束点需要多少步。可以左走一步,右走一步,或者坐标乘2.
思路:裸的bfs啊,水题一枚。
代码:
#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 100000;
int flag[N];
struct point{
int num,cnt;
}pp[N+5];
int bfs(int begin,int end){
queue<int> qq;
CLR(flag,0);
qq.push(begin);
flag[begin] = 1;
pp[begin].cnt = 0;
while(1){
int x = qq.front();
qq.pop();
//printf("x = %d\n",x);
if(x == end)
break;
if(x - 1 >= 0 && x - 1 <= N && !flag[x-1]){
qq.push(x-1);
flag[x-1] = true;
pp[x-1].cnt = pp[x].cnt + 1;
}
if(x+1 >= 0 && x+1 <= N && !flag[x+1]){
qq.push(x+1);
flag[x+1] = true;
pp[x+1].cnt = pp[x].cnt + 1;
}
if(2 * x >= 0 && 2 * x <= N && !flag[2*x]){
qq.push(2*x);
flag[2*x] = true;
pp[2*x].cnt = pp[x].cnt + 1;
}
}
return pp[end].cnt;
}
int main(){
int begin,end;
while(scanf("%d%d",&begin,&end) != EOF){
int x = bfs(begin,end);
printf("%d\n",x);
}
return 0;
}
分享到:
相关推荐
北大POJ3278-Catch That Cow 解题报告+AC代码
搜索......................................................
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3267-The Cow Lexicon
北大POJ3267-The Cow Lexicon 解题报告+AC代码
Net<br>Pku acm 3278 Catch That Cow Pku acm 2253 Frogger Pku acm 1062 昂贵的聘礼 Pku acm 1125 Stockbroker Grapevine Pku acm 1611 The Suspects Pku acm 2492 A Bug's Life 更多请访问:...
北大POJ3176-Cow Bowling
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ3176-Cow Bowling 解题报告+AC代码
poj 1989 The Cow Lineup.md
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
poj 3623 Best Cow Line, Gold.md
poj 3266 Cow School.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
通过学习STL中的队列的实现原理解决了一道应用题:北大poj网上的Catch That Cow题目。还有最小生成树的应用的课程设计
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1016-Numbers That Count【字符串处理】 解题报告+AC代码
BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索+剪枝) POJ 1416 POJ 2676 POJ 1129:white_question_mark: 数据结构 串 POJ 1016 POJ 1035 POJ ...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ 3131 双向BFS解立体八数码问题