题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1495
思路
首先 如果可乐的体积 是奇数 那么是无解的
然后 如果能够得到两杯 都是一般容量的可乐 那么一定是装在 原来那个可乐被子 以及 大一点的杯子当中
要找最少步骤 容易知道 用 BFS
每次转移的状态有 s -> n s -> m n -> s n -> m m -> s m -> n 用 vis 标记 状态
最后如果满足条件 就return
当然 即使可乐体积是偶数 也有可能 是没有办法满足条件的 也就是要设置一个哨兵
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 <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, 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); const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 1e2 + 5; const int MOD = 1e9 + 7; struct node { int s, n, m, t; }; int s, n, m; int vis[maxn][maxn]; int bfs() { queue <node> q; CLR(vis); node temp; temp.s = s; temp.n = 0; temp.m = 0; temp.t = 0; vis[n][m] = 1; q.push(temp); while (!q.empty()) { node u = q.front(), v; q.pop(); if (u.n == s / 2 && u.s == s / 2) return u.t; if (u.s && u.n != n) // s -> n { int c = n - u.n; if (u.s >= c) { v.s = u.s - c; v.n = n; } else { v.s = 0; v.n = u.n + u.s; } v.m = u.m; if (vis[v.n][v.m] == 0) { v.t = u.t + 1; q.push(v); vis[v.n][v.m] = 1; } } if (u.s && u.m != m) // s -> m { int c = m - u.m; if (u.s >= c) { v.s = u.s - c; v.m = m; } else { v.s = 0; v.m = u.m + u.s; } v.n = u.n; if (vis[v.n][v.m] == 0) { v.t = u.t + 1; q.push(v); vis[v.n][v.m] = 1; } } if (u.n && u.s != s) // n -> s { int c = s - u.s; if (u.n >= c) { v.n = u.n - c; v.s = s; } else { v.n = 0; v.s = u.s + u.n; } v.m = u.m; if (vis[v.n][v.m] == 0) { v.t = u.t + 1; q.push(v); vis[v.n][v.m] = 1; } } if (u.n && u.m != m) // n -> m { int c = m - u.m; if (u.n >= c) { v.n = u.n - c; v.m = m; } else { v.n = 0; v.m = u.m + u.n; } v.s = u.s; if (vis[v.n][v.m] == 0) { v.t = u.t + 1; q.push(v); vis[v.n][v.m] = 1; } } if (u.m && u.s != s) // m -> s { int c = s - u.s; if (u.m >= c) { v.m = u.m - c; v.s = s; } else { v.m = 0; v.s = u.s + u.m; } v.n = u.n; if (vis[v.n][v.m] == 0) { v.t = u.t + 1; q.push(v); vis[v.n][v.m] = 1; } } if (u.m && u.n != n) // m -> n { int c = n - u.n; if (u.m >= c) { v.m = u.m - c; v.n = n; } else { v.m = 0; v.n = u.n + u.m; } v.s = u.s; if (vis[v.n][v.m] == 0) { v.t = u.t + 1; q.push(v); vis[v.n][v.m] = 1; } } } return 0; } int main() { while (scanf("%d%d%d", &s, &n, &m) && (s || n || m)) { if (s & 1) puts("NO"); else { if (n < m) swap(n, m); int ans = bfs(); if (ans) cout << ans << endl; else puts("NO"); } } }转载于:https://www.cnblogs.com/Dup4/p/9433132.html
相关资源：JAVA上百实例源码以及开源项目