uva 571(bfs)

题意：就是倒水游戏，有两个杯子无限水可以进行三种操作：
一个杯子装满水，一个杯子倒光，一个杯子倒到另一个杯子。
最后要求其中一个杯子的水量到n，然后输出步骤。
思路:bfs即可，最后递归输出。
代码如下：
  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-03-28 18:49
  5  * Filename     : uva_571.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<ll, int> pli;
 29 typedef pair<int, ll> pil;
 30 
 31 const int INF = 0x3f3f3f3f;
 32 const double eps = 1E-6;
 33 const int LEN = 1010;
 34 int ca, cb, n;
 35 pii vis[LEN][LEN];
 36 
 37 pii empty(pii x, int a){
 38     if(a == 0)return MP(0, x.second);
 39     else return MP(x.first, 0);
 40 }
 41 
 42 pii fill(pii x, int a){
 43     if(a == 1) return MP(x.first, cb);
 44     else return MP(ca, x.second);
 45 }
 46 
 47 pii pour(pii x, int a, int b){
 48     int tmp = x.first + x.second;
 49     if(a == 0 && b == 1){
 50          if(tmp <= cb) return MP(0, tmp);
 51          else return MP(tmp - cb, cb);
 52     }else{
 53         if(tmp <= ca) return MP(tmp, 0);
 54         else return MP(ca, tmp - ca);
 55     }
 56 } 
 57 
 58 void flush(pii nvex, pii nv, queue<pii> &q){
 59     if(vis[nv.first][nv.second].first == -1){
 60         vis[nv.first][nv.second] = nvex;
 61         q.push(nv);
 62     }
 63 }
 64 
 65 pii bfs(){
 66     memset(vis, -1, sizeof vis);
 67     queue<pii> q;
 68     q.push(MP(0, 0));
 69     vis[0][0] = MP(0, 0);
 70     while(!q.empty()){
 71         pii nvex = q.front(), nv; q.pop();
 72         if(nvex.first == n || nvex.second == n) return nvex;
 73         nv = empty(nvex, 0);flush(nvex, nv, q);
 74         nv = empty(nvex, 1);flush(nvex, nv, q);
 75         nv = fill(nvex, 0);flush(nvex, nv, q);
 76         nv = fill(nvex, 1);flush(nvex, nv, q);
 77         nv = pour(nvex, 0, 1);flush(nvex, nv, q);
 78         nv = pour(nvex, 1, 0);flush(nvex, nv, q);
 79     }
 80     return MP(-1, -1);
 81 }
 82 
 83 void out(int x, int y){
 84     pii nv, nvex = vis[x][y];
 85     if(vis[x][y] == MP(x, y)) return ;
 86     int op;
 87     nv = empty(nvex, 0); if(nv == MP(x, y)) op = 1;
 88     nv = empty(nvex, 1); if(nv == MP(x, y)) op = 2;
 89     nv = fill(nvex, 0); if(nv == MP(x, y)) op = 3;
 90     nv = fill(nvex, 1); if(nv == MP(x, y)) op = 4;
 91     nv = pour(nvex, 0, 1); if(nv == MP(x, y)) op = 5;
 92     nv = pour(nvex, 1, 0); if(nv == MP(x, y)) op = 6;
 93     out(vis[x][y].first, vis[x][y].second);
 94     switch(op){
 95         case 1: cout << "empty A" << endl;break;
 96         case 2: cout << "empty B" << endl;break;
 97         case 3: cout << "fill A" << endl;break;
 98         case 4: cout << "fill B" << endl;break;
 99         case 5: cout << "pour A B" << endl; break;
100         case 6: cout << "pour B A" << endl; break;
101     }
102 }
103 
104 int main()
105 {
106     //freopen("in.txt", "r", stdin);
107 
108     ios::sync_with_stdio(false);
109     while(cin >> ca >> cb >> n){
110         pii pos = bfs();
111         out(pos.first, pos.second);
112         cout << "success" << endl;
113     }
114     return 0;
115 }
View Code