题目链接
题意
有两个容量分别为ca,cb的杯子，可以向杯子里倒水，将杯子里的水倒空，将一个杯子里的水倒到另一个杯子里，求怎样倒才能使其中的一个杯子里的水恰为N加仑。
思路
两个杯子里的水量组成一个状态，不断地进行题中的6种操作来扩展状态结点进行bfs，直到其中一个杯子的水量为N即可。
代码
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 struct Node 9 { 10 int a, b; 11 int flag; 12 Node* pre; 13 }; 14 15 const int N = 1010; 16 int ca, cb, n; 17 int visit[N][N]; 18 stack s; 19 20 void print() 21 { 22 while (!s.empty()) 23 { 24 switch (s.top()) 25 { 26 case 0: 27 cout << "fill A" << endl; 28 break; 29 case 1: 30 cout << "fill B" << endl; 31 break; 32 case 2: 33 cout << "empty A" << endl; 34 break; 35 case 3: 36 cout << "empty B" << endl; 37 break; 38 case 4: 39 cout << "pour A B" << endl; 40 break; 41 case 5: 42 cout << "pour B A" << endl; 43 break; 44 } 45 s.pop(); 46 } 47 cout << "success" << endl; 48 } 49 50 void bfs(int a, int b) 51 { 52 Node state[N]; 53 int cnt = -1; 54 memset(visit, 0, sizeof(visit)); 55 Node node; 56 node.a = node.b = 0; 57 node.pre = NULL; 58 queue q; 59 q.push(node); 60 visit[node.a][node.b] = 1; 61 while (!q.empty()) 62 { 63 Node node = q.front(); 64 q.pop(); 65 state[++cnt] = node; 66 Node next = node; 67 for (int i = 0; i < 6; i++) 68 { 69 next = node; 70 int amount; 71 switch (i) 72 { 73 case 0: //fill a 74 next.a = ca; 75 next.flag = 0; 76 break; 77 case 1: //fill b 78 next.b = cb; 79 next.flag = 1; 80 break; 81 case 2: // empty a 82 next.a = 0; 83 next.flag = 2; 84 break; 85 case 3: //empty b 86 next.b = 0; 87 next.flag = 3; 88 break; 89 case 4: //pour a b 90 amount = cb - node.b; 91 if (node.a > amount) 92 { 93 next.a -= amount; 94 next.b = cb; 95 } 96 else { 97 next.a = 0; 98 next.b = node.a + node.b; 99 }100 next.flag = 4;101 break;102 case 5: //pour b a103 amount = ca - node.a;104 if (node.b > amount)105 {106 next.a = ca;107 next.b -= amount;108 }109 else {110 next.a = node.a + node.b;111 next.b = 0;112 }113 next.flag = 5;114 break;115 }116 117 if (!visit[next.a][next.b])118 {119 visit[next.a][next.b] = 1;120 next.pre = &state[cnt];121 if (next.a==n || next.b == n)122 {123 while (next.pre)124 {125 s.push(next.flag);126 next = *next.pre;127 }128 print();129 return;130 }131 q.push(next);132 }133 }134 }135 }136 137 int main()138 {139 //freopen("poj1606.txt", "r", stdin);140 while (cin >> ca >> cb >> n)141 {142 bfs(0, 0);143 }144 return 0;145 }
相似题目
1、