poj 3414BFS

cavenkaka

   题意：给出两个容积分别为 a 和 b 的pot，按照以下三种操作方式，求出能否在一定步数后，使者两个pot的其中一个的水量为c。
      1.FILL(i)：将ipot倒满水。
      2.DROP(i)：将ipot倒空水。
      3.POUR(i,j)： 将ipot的水倒到jpot上，直至要么ipot为空，要么jpot为满。
  思路：bfs求最短路径，与1426类似，只是每个节点的子节点数为6个而已。
代码如下：
#include<iostream>using namespace std;const int Max = 101; struct node{    int ope;  int a;  int b;  node *pre;}que[Max * Max];  //  队列结点，ope记录第几种操作，a,b记录此结点两个pot的水的数量。bool vis[Max][Max];char str[6][10] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"}; // 各操作对应输出的字符串。 int min(int a, int b){    return a < b ? a : b;} void print(node now){    if(now.pre != NULL){        print(*now.pre);        cout << str[now.ope] << endl;    }}//递归输出答案个人认为写得很巧妙 void bfs(int a, int b, int c){    int steps = 0;    int head = 0, tail = 1;    que[0].a = que[0].b = 0;    que[0].pre = NULL;     while(tail - head > 0){        int count = tail - head;        while(count --)//每一种情况都要考虑六种情况{            node now = que[head];            if(now.a == c || now.b == c){                cout << steps << endl;                print(now);                return;            }            if(!vis[a][now.b]){                que[tail].ope = 0;                que[tail].a = a;                que[tail].b = now.b;                que[tail].pre = &que[head];                vis[a][now.b] = true;                tail ++;            }            if(!vis[now.a][b]){                que[tail].ope = 1;                que[tail].a = now.a;                que[tail].b = b;                que[tail].pre = &que[head];                vis[now.a][b] = true;                tail ++;            }            if(!vis[0][now.b]){                que[tail].ope = 2;                que[tail].a = 0;                que[tail].b = now.b;                que[tail].pre = &que[head];                vis[0][now.b] = true;                tail ++;            }           if(!vis[now.a][0])   {                que[tail].ope = 3;                que[tail].a = now.a;                que[tail].b = 0;                que[tail].pre = &que[head];                vis[now.a][0] = true;                tail ++;            }            int wat1 = min(now.a, b - now.b);            if(!vis[now.a - wat1][now.b + wat1]){                que[tail].ope = 4;                que[tail].a = now.a - wat1;                que[tail].b = now.b + wat1;                que[tail].pre = &que[head];                vis[now.a - wat1][now.b + wat1] = true;                tail ++;            }            int wat2 = min(a - now.a, now.b);            if(!vis[now.a + wat2][now.b - wat2]){                que[tail].ope = 5;                que[tail].a = now.a + wat2;                que[tail].b = now.b - wat2;                que[tail].pre = &que[head];                vis[now.a + wat2][now.b - wat2] = true;                tail ++;            }            head ++;        }        steps ++;    }    cout << "impossible" << endl;} int main(){    int a, b, c;    cin >> a >> b >> c;    memset(vis, false, sizeof(vis));//初始化    vis[0][0] = true;//初始化    bfs(a, b, c);    return 0;}