POJ - 3278 Catch That Cow 【BFS】
2024-10-21 11:57:20
题目链接
http://poj.org/problem?id=3278
题意
给出两个数字 N K 每次 都可以用三个操作 + 1 - 1 * 2
求 最少的操作次数 使得 N 变成 K
思路
BFS 但是要注意 设置 数组的范围 小心 RE
AC代码
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define CLR(a, b) memset(a, (b), sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
const double PI = acos(-1.0);
const double E = exp(1.0);
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const int MOD = 1e9 + 7;
int n, k;
int ans;
int v[maxn];
struct node
{
int v, step;
};
bool ok(int x)
{
if (x < 0 || x > maxn)
return false;
return true;
}
void bfs()
{
CLR(v, 0);
queue <node> q;
node tmp;
tmp.v = n;
tmp.step = 0;
q.push(tmp);
v[n] = 1;
while (!q.empty())
{
node u = q.front(), V;
q.pop();
if (u.v == k)
{
ans = u.step;
return;
}
V.step = u.step + 1;
V.v = u.v + 1;
if (ok(V.v) && v[V.v] == 0)
{
q.push(V);
v[V.v] = 1;
}
V.v = u.v - 1;
if (ok(V.v) && v[V.v] == 0)
{
q.push(V);
v[V.v] = 1;
}
V.v = u.v * 2;
if (ok(V.v) && v[V.v] == 0)
{
q.push(V);
v[V.v] = 1;
}
}
}
int main()
{
scanf("%d%d", &n, &k);
ans = INF;
bfs();
cout << ans << endl;
}
最新文章
- php图片处理类库 Image
- mysql hang and srv_error_monitor_thread using 100% cpu
- C++ Primer : 第十三章 : 拷贝控制之对象移动
- java 进程启用远程查看
- JQuery 简单的文字超出部分隐藏下拉显示
- 如何在eclipse中使用XYLayout布局?在此介绍如何把XYLayout导入到eclipse .
- Java for LeetCode 169 Majority Element
- Wordpress添加关键词和描述
- 配置sshd_config中的PermitRootLogin设置root登录或者禁止root登录
- sqlserver insert into select
- Ubuntu环境下手动配置openSSH
- JS获取客户端IP地址、MAC和主机名七种方法
- 如何去除configure的默认选择-g O2
- uva140
- Python+reuqests自动化接口测试
- 【BZOJ2242】【SDOI2011】计算器
- hibernate一级缓存及对象的状态
- Altium Designer 放置机械孔
- 基于springboot的SSM框架实现返回easyui-tree所需要数据
- 通行导论-IP数据网络基础(2)
热门文章
- osgcuda 【转】
- hdu 5381 The sum of gcd(线段树+gcd)
- 2017.2.20 activiti实战--第五章--用户与组及部署管理(一)用户与组
- Ubuntu 14.04 使用VirtualBox 4.3.10 虚拟 Windows 7
- 新版本号的tlplayer for android ,TigerLeapMC for windows公布了
- show processlist 各个状态说明
- vue2.X computed 计算属性
- vue-cli配置文件详解
- HTTP学习笔记(一)报文和连接管理
- 【Excle数据透视】如何在数据透视表字段列表中显示更多的字段