HDU 1495 非常可乐——bfs

HDU 1495 非常可乐——bfs

#include #include #include #include #include using namespace std;const int maxn = 110;bool vis[maxn][maxn][maxn];int S, A, B;struct State { int s, a, b, step;}state;queue q;void solve(int &x, int X, int &y, int Y) { if (X - x <= y) { y = y - X + x; x = X; } else { x = x + y; y = 0; }}void add(int s, int a, int b, int step) { if (!vis[s][a][b]) { vis[s][a][b] = true; q.push(State{s, a, b, step}); }}void bfs() { int target = S>>1, ans = -1; memset(vis, false, sizeof(vis)); vis[S][0][0] = true; while (!q.empty()) q.pop(); q.push(State{S, 0, 0, 0}); while (!q.empty()) { state = q.front(); q.pop(); if (state.s == target && state.a == target) { ans = state.step; break; } int s, a, b; s = state.s, a = state.a, b = state.b; solve(a, A, s, S); add(s, a, b, state.step + 1); s = state.s, a = state.a, b = state.b; solve(b, B, s, S); add(s, a, b, state.step + 1); s = state.s, a = state.a, b = state.b; solve(b, B, a, A); add(s, a, b, state.step + 1); s = state.s, a = state.a, b = state.b; solve(s, S, a, A); add(s, a, b, state.step + 1); s = state.s, a = state.a, b = state.b; solve(s, S, b, B); add(s, a, b, state.step + 1); s = state.s, a = state.a, b = state.b; solve(a, A, b, B); add(s, a, b, state.step + 1); } if (ans == -1) printf("NO\n"); else printf("%d\n", ans);}int main() { while (~scanf("%d %d %d", &S, &A, &B) && (S || A || B)) { if (A < B) swap(A, B); if (S % 2) printf("NO\n"); else bfs(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。