题目链接
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; }转载于:https://www.cnblogs.com/Dup4/p/9433111.html
