本文主要是介绍USACO Mother's Milk,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意 :有3个杯子,问当a杯子为空时,c杯子能够装多少种体积的水
思路 :倒水问题,有广搜,对于当前,接下来有6种状态:a到给b,a到给c ,c到给b,c到给a,b到给a, b到给c。每一种状态又有两种情况:能装满和不能装满。这里还要注意一点就是必须判断重复,即防止a倒给b,然后b再倒给a这种情况的发生!
这里还有一个节省代码的技巧:因为情况很多,一开始我使用6个if,结果代码写的老长,十分不方便debug。我们可以使用for循环,在控制是哪个杯子时我是用了模运算,具体实现请看代码,我觉得写的还不错哦!
代码:
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cstdio>
#define N 29using namespace std;bool v[N][N];
typedef struct
{int w[3];
}milk;int bfs( milk start, int *ans )
{int times = 0;milk now;now.w[0] = now.w[1] = 0;now.w[2] = start.w[2];queue <milk> q;memset( v, false, sizeof( v ) );v[0][0] = true;q.push( now );while( !q.empty() ){now = q.front();q.pop();milk t;for( int i = 0; i < 3; i++ ){if( now.w[i] > 0 ){for( int j = i + 1; j < i + 3; j++ ){t = now;if( now.w[i] >= start.w[j%3] - now.w[j%3] ){t.w[i] = now.w[i] - ( start.w[j%3] - now.w[j%3] );t.w[j%3] = start.w[j%3];}else{t.w[i] = 0;t.w[j%3] = now.w[j%3] + now.w[i];}if( !v[t.w[0]][t.w[1]] ){if( t.w[0] == 0 ){ans[times++] = t.w[2];}v[t.w[0]][t.w[1]] = true;q.push( t );}}}}}return times;
}int main()
{freopen( "milk3.in", "r", stdin );freopen( "milk3.out", "w", stdout );milk start;while( cin >> start.w[0] >> start.w[1] >> start.w[2] ){int ans[N];int times = bfs( start, ans );sort( ans, ans + times );for( int i = 0; i < times; i++ ){cout << ans[i] << ' ';}cout << start.w[2] << '\n';}return 0;
}
这篇关于USACO Mother's Milk的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!