扩展 amount ase ref turn mem cin eof include
题目链接
http://poj.org/problem?id=1606
题意
有两个容量分别为ca,cb的杯子,可以向杯子里倒水,将杯子里的水倒空,将一个杯子里的水倒到另一个杯子里,求怎样倒才能使其中的一个杯子里的水恰为N加仑。
思路
两个杯子里的水量组成一个状态,不断地进行题中的6种操作来扩展状态结点进行bfs,直到其中一个杯子的水量为N即可。
代码
- #include < iostream > #include < cstdio > #include < cstring > #include < queue > #include < stack > using namespace std;
- struct Node {
- int a,
- b;
- int flag;
- Node * pre;
- };
- const int N = 1010;
- int ca,
- cb,
- n;
- int visit[N][N];
- stack < int > s;
- void print() {
- while (!s.empty()) {
- switch (s.top()) {
- case 0:
- cout << "fill A" << endl;
- break;
- case 1:
- cout << "fill B" << endl;
- break;
- case 2:
- cout << "empty A" << endl;
- break;
- case 3:
- cout << "empty B" << endl;
- break;
- case 4:
- cout << "pour A B" << endl;
- break;
- case 5:
- cout << "pour B A" << endl;
- break;
- }
- s.pop();
- }
- cout << "success" << endl;
- }
- void bfs(int a, int b) {
- Node state[N];
- int cnt = -1;
- memset(visit, 0, sizeof(visit));
- Node node;
- node.a = node.b = 0;
- node.pre = NULL;
- queue < Node > q;
- q.push(node);
- visit[node.a][node.b] = 1;
- while (!q.empty()) {
- Node node = q.front();
- q.pop();
- state[++cnt] = node;
- Node next = node;
- for (int i = 0; i < 6; i++) {
- next = node;
- int amount;
- switch (i) {
- case 0:
- //fill a
- next.a = ca;
- next.flag = 0;
- break;
- case 1:
- //fill b
- next.b = cb;
- next.flag = 1;
- break;
- case 2:
- // empty a
- next.a = 0;
- next.flag = 2;
- break;
- case 3:
- //empty b
- next.b = 0;
- next.flag = 3;
- break;
- case 4:
- //pour a b
- amount = cb - node.b;
- if (node.a > amount) {
- next.a -= amount;
- next.b = cb;
- } else {
- next.a = 0;
- next.b = node.a + node.b;
- }
- next.flag = 4;
- break;
- case 5:
- //pour b a
- amount = ca - node.a;
- if (node.b > amount) {
- next.a = ca;
- next.b -= amount;
- } else {
- next.a = node.a + node.b;
- next.b = 0;
- }
- next.flag = 5;
- break;
- }
- if (!visit[next.a][next.b]) {
- visit[next.a][next.b] = 1;
- next.pre = &state[cnt];
- if (next.a == n || next.b == n) {
- while (next.pre) {
- s.push(next.flag);
- next = *next.pre;
- }
- print();
- return;
- }
- q.push(next);
- }
- }
- }
- }
- int main() {
- //freopen("poj1606.txt", "r", stdin);
- while (cin >> ca >> cb >> n) {
- bfs(0, 0);
- }
- return 0;
- }
poj1606 Jugs
扩展 amount ase ref turn mem cin eof include
原文:http://www.cnblogs.com/sench/p/7875094.html
来源: http://www.bubuko.com/infodetail-2403277.html