这是一道对于初学BFS而言较复杂的题目，虽然整体上，bfs的方法没有太大的变化，但的确如果想要在初学阶段将其理解，并做出一定的总结，一定会使得这道题目发挥出超其本身的价值和内容。

此题目：细心，冷静，多思考。

当然，由于我比较菜，各种错误和疏忽不断出现，所以此题花费了较长的时间，约5h，并在最后的两个小时内参考了他人的代码。。。

Pots

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 31113 Accepted: 12915 Special Judge

Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

  1. FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
  2. DROP(i) empty the pot i to the drain;
  3. POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

Source

Northeastern Europe 2002, Western Subregion

题目的中文大约是：给定两个容积为a，b的水壶，初始状态为空；再给一个水量c。每次操作可以如下进行：

  1. 将壶1或者壶2填满；
  2. 将壶1或者壶2全部倒掉；
  3. 将一个壶中的水导入另一个壶中（能倒入多少就倒入多少，当然其中一个壶不能是空的，另一个不能是满的）

输入abc，需要你输出当其中一个水壶的水量达到c时所用的次数与倾倒步骤打印出来；当然如果永远达不到c的话，输出impossible即可。

tips：多组输入，c符合规范。

emm，不妨以此题目为例，梳理一下[[bfs]]的做法好了。

首先我们要判断这道题目是[[bfs]]，从题目中可以清楚看出，求最短路径，每次的操作是固定的那么基本上就可以用bfs去解决。先看一般，再看特殊的地方需要什么东西来解决（比如题目所求的cnt，步骤）

  1. 确定一个状态包括了什么：比如，有的题目仅仅需要该点的位置，有的题目还需要其他的东西；只能具体问题具体分析了。在此题目中，我们可以看到一个状态就是我们的a，b两个水壶的储水量。

    那么我们将其设定为一个struct node即可包括 两个int 代表两个水壶的储水量。

    特别是考虑到本题目需要cnt和倒水的步骤，那么我们在每个状态里的的步骤都是不一样的，就用string 储存吧，然后每一个步骤添加的时候记得加上换行符号”\n”;

    struct node
{
    int x;
    int y;
    string s;
    int cnt;
};

  1. 寻找vis范围，确定了总的范围我们才可以利用vis来判断我们是否踩过这个点，这也是最有效的方法来避免死循环,也是迫使队列结束的好方法。有题目给出的“These are all integers in the range from 1 to 100 and C≤max(A,B).”所以我们知道a有100种可能，b也是。（小提示，如果你发现有题目似乎用不到vis那么大概也许可能他不一定需要使用bfs来解题）

    bool vis[101][101];

    对了，记住此题目是多行输入，意味着如果你的vis不及时初始化就会fc

    在这里初始化 vis 可以使用memset，常见用法是这样。

    #define CLR(x,y) memset(x,y,sizeof(x))
CLR(vis,false);

  2. 找到起点和终点的状态。终点顾名思义其中有一个水壶的储水量是c的时候就代表了end，而开始我们发现他给定的是两个空的水壶，所以我们给定一个node 初始化全0,记得标记vis是1，然后将其推到队列里作为起始点。

      queue<node> q;
   
   node t;
   t.cnt=0;
   t.x=0;
   t.y=0;
   t.s="";
vis[0][0]=1;
   q.push(t);

    但，不难发现，第一步的走法其实只有给两个壶其中之一填满。所以我们也可以是将其设为两个初始点，添加到队列其中去，但是记得更改相关的数值，参考下code。

    node t;
   t.cnt =1;
   t.x = a;
   t.y = 0;
   t.s = "FILL(1)\n";
   q.push(t);
   
   vis[a][0] =1;
   t.cnt =1;
   t.x = 0;
   t.y = b;
   t.s = "FILL(2)\n";
   vis[0][b] = 1;
   q.push(t);

    当然，两者的区别并不是很大，选择前者更容易理解一些，也更加符合一般的bfs的要求。

  3. 下面就要进入queue队列的循环中去咯~

    进入循环当然先把front给从队列中打捞出来。

    while(!q.empty()){
        node front  = q.front();
        q.pop();
        t = front;

    这里的t 是借用了上面的t实际上,我们往往是重新node next 的做法往往更普遍一些。

    有了 此次开头的中心点，我们就要赶紧确定什么时候能结束了，万一我们直接就出去了呢哈哈。

    if(front.x ==c||front.y ==c){
            cnt = t.cnt;
            cout<<cnt<<"\n";
            cout<<front.s;
            break;
        }

    这里有一丝丝的玄机，因为这里采用了break，所以我们在最后bfs返回的是cnt的值，所以我们要将cnt给赋值了，才能return 回去。虽然我们在这里就输出了cnt，但返回的cnt是用来判断我们是否是impossible，如果我们一直没有找到使得题目成立条件，而队列走走完了，那我们就一直没有给cnt赋过值，所以我们自然是返回的是0 那么，就可在main函数中做出特判。

  4. 接下来就是几种动作的出现，其实就是6种

    FILL(1),FILL(2),DROP(1),DROP(2),POUR(1,2),POUR(2,1)

    我们在对其分别进行情况的判定，然后一一进行就可以了。当然这个过程是艰苦的，如果在一些相似的地方没有思考清楚而是cv的话，容易由于没有看清而出现许多问题。所以奥里给，这一部分需要认真一些。

    对了，我们在前面看到我们既然进行到了这一步，一定是出不去了所以front.cnt++；

    front.cnt ++;
        //fill
         t = front;
        if((front.x!=a) && (!vis[a][front.y])){// 
            t.x = a;
            t.y = front.y;
            t.s =front.s + "FILL(1)\n";
            
            q.push(t);
            vis[a][t.y] = 1;
        }
        if((front.y!=b) &&(!vis[front.x][b])){
            t.x = front.x;
            t.y = b;
            t.s =front.s + "FILL(2)\n";
            
            q.push(t);
            vis[t.x][b] = 1;
        }
        //pour
        if((front.x) && (front.y!=b)){//因为我们pour有两种情况，b被倒满或倒不满，所以我们最好放到里面去判断vis
            if(front.x>=(b-front.y)&&front.x){
                t.y = b;
                t.x = front.x - (b-front.y);
            }
            else {
                t.y = front.y + front.x;
                t.x = 0;   
            }
                t.s = front.s + "POUR(1,2)\n";
                if(!vis[t.x][t.y])
                q.push(t);
                vis[t.x][t.y] = 1;
        }
        if((front.y) && (front.x!=a)){//因为我们pour有两种情况，a被倒满或倒不满，所以我们最好放到里面去判断vis
            if(front.y>=(a-front.x) && front.y){
                t.y = front.y -(a - front.x); 
                t.x = a;
            }
            else {
                t.x = front.x+ front.y;
                t.y = 0;
            }
                t.s = front.s + "POUR(2,1)\n";
                if(!vis[t.x][t.y])
                
                q.push(t);
                vis[t.x][t.y] = 1;
        }
        //drop
        if((front.x)&&(!vis[0][front.y])){
            t.x = 0;
            t.y = front.y;
            t.s = front.s + "DROP(1)\n";
            vis[0][t.y] = 1;
            
            q.push(t);
        }
        if((front.y)&&(!vis[front.x][0])){
            t.x = front.x;//cv makes me forget it!!!
            t.y = 0;
            t.s = front.s + "DROP(2)\n";
            vis[t.x][0] = 1;        
            q.push(t);
        }     
    }

最后return cnt;就可以结束这个bfs了。小心，因为代码过长，一处很小的错误可能就会gg。

完整的代码

对，你没有看错，两套代码，中英双文嘿嘿，两种代码其实在一些小的方面有所不同，参考第一个即可，第二个是他人代码（出处已不可寻）


#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
#define CLR(x,y) memset(x,y,sizeof(x))
int a,b,c;
struct node
{
    int x;
    int y;
    string s;
    int cnt;
};
bool vis[101][101];
int bfs(){
    int cnt =0;
    CLR(vis,false);
    queue<node> q;

    node t;
    t.cnt=0;
    t.x=0;
    t.y=0;
    t.s="";
    vis[0][0] =1;
    q.push(t);
    while(!q.empty()){
        node front  = q.front();
        q.pop();
        t = front;
        if(front.x ==c||front.y ==c){
            cnt = t.cnt;
            cout<<cnt<<"\n";
            cout<<front.s;
            break;
        }
        front.cnt ++;
        //fill
         t = front;
        if((front.x!=a) && (!vis[a][front.y])){// <?
            t.x = a;
            t.y = front.y;
            t.s =front.s + "FILL(1)\n";
            
            q.push(t);
            vis[a][t.y] = 1;
        }
        if((front.y!=b) &&(!vis[front.x][b])){
            t.x = front.x;
            t.y = b;
            t.s =front.s + "FILL(2)\n";
            
            q.push(t);
            vis[t.x][b] = 1;
        }
        //pour
        if((front.x) && (front.y!=b)){//因为我们pour有两种情况，b被倒满或倒不满，所以我们最好放到里面去判断vis
            if(front.x>=(b-front.y)&&front.x){
                t.y = b;
                t.x = front.x - (b-front.y);
            }
            else {
                t.y = front.y + front.x;
                t.x = 0;   
            }
                t.s = front.s + "POUR(1,2)\n";
                if(!vis[t.x][t.y])
                q.push(t);
                vis[t.x][t.y] = 1;
        }
        if((front.y) && (front.x!=a)){//因为我们pour有两种情况，a被倒满或倒不满，所以我们最好放到里面去判断vis
            if(front.y>=(a-front.x) && front.y){
                t.y = front.y -(a - front.x); 
                t.x = a;
            }
            else {
                t.x = front.x+ front.y;
                t.y = 0;
            }
                t.s = front.s + "POUR(2,1)\n";
                if(!vis[t.x][t.y])
                
                q.push(t);
                vis[t.x][t.y] = 1;
        }
        //drop
        if((front.x)&&(!vis[0][front.y])){
            t.x = 0;
            t.y = front.y;
            t.s = front.s + "DROP(1)\n";
            vis[0][t.y] = 1;
            
            q.push(t);
        }
        if((front.y)&&(!vis[front.x][0])){
            t.x = front.x;//cv makes me forget it!!!
            t.y = 0;
            t.s = front.s + "DROP(2)\n";
            vis[t.x][0] = 1;        
            q.push(t);
        }     
    }
    return cnt;

}
int main(){
    while ((cin>>a>>b>>c))
    {
        if(bfs()==0)cout<<"impossible"<<endl;
    }
    
    return 0;
}
//personal code.

/*
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))

int n , m , x;
bool vis[200][200];
//图上所有点的取值区域可用 a，b的不同的水量状态表示！
struct nodes{
	int x, y;
	string step;
	int cnt;
};
 
int bfs() {
	int cnt = 0;
	CLR(vis, 0);//init
	queue<nodes> q;
	nodes nd1;

	nd1.x = 0;//(init)
	nd1.y = 0;
	nd1.cnt = 0;
    nd1.step = "";
	q.push(nd1);
	vis[0][0]=1;
	
	while(!q.empty()) {
		nodes nd = q.front();
		q.pop();
		if (nd.x == x || nd.y == x) {// end
			cnt = nd.cnt;
			cout<<cnt<<"\n";// it looks like nothing at all. However this cnt is connect to the return value!
                            //there is one possible thing is that we could at the last step that we find the right idea!
			cout<<nd.step;
			break;
		}
		++nd.cnt;// every time the nd will be renew one as front;
		nodes nd2;//as next
		nd2.cnt = nd.cnt; 
		if (nd.x < n && !vis[n][nd.y]) {//if fronter is not full&& not visit the status when it is full
			nd2.x = n;
			nd2.y = nd.y;
			nd2.step = nd.step + "FILL(1)\n";
			q.push(nd2);
			vis[nd2.x][nd2.y] = 1;
		}
		if (nd.y < m && !vis[nd.x][m]) {
			nd2.x = nd.x;
			nd2.y = m;
			nd2.step = nd.step + "FILL(2)\n";
			q.push(nd2);
			vis[nd2.x][nd2.y] = 1;
		}
		
		if (nd.x > 0 && nd.y != m) {//when a is not a empty one && b is not full
			if (nd.x >= (m - nd.y) && nd.x != 0) {//if a couldn't pour it's all to b
				nd2.x = (nd.x - (m - nd.y));// a will pour as more as it could 
				nd2.y = m;				
			} 
            else {//a could pour all to b
				nd2.y = (nd.x + nd.y);
				nd2.x = 0;
			}

			if (!vis[nd2.x][nd2.y]) {
				nd2.step = nd.step + "POUR(1,2)\n";
				q.push(nd2);
				vis[nd2.x][nd2.y] = 1;
			}
			
		}
		
		if (nd.y > 0 && nd.x != n) {//pour b to a
			if (nd.y >= (n - nd.x) && nd.y != 0) {
				nd2.y = (nd.y - (n - nd.x));
				nd2.x = n;
			} else {
				
				nd2.x = (nd.y + nd.x);
				nd2.y = 0;
			}
			if (!vis[nd2.x][nd2.y]) {
				nd2.step = nd.step + "POUR(2,1)\n";
				q.push(nd2);
				vis[nd2.x][nd2.y] = 1;	
			}
		}
		
		if (nd.x > 0 && !vis[0][nd.y]) {//a is not empty
			nd2.x = 0;
			nd2.y = nd.y;
			nd2.step = nd.step + "DROP(1)\n";
			q.push(nd2);
			vis[nd2.x][nd2.y] = 1;
		}
		if (nd.y > 0 && !vis[nd.x][0]) {
			nd2.x = nd.x;
			nd2.y = 0;
			nd2.step = nd.step + "DROP(2)\n";
			q.push(nd2);
			vis[nd2.x][nd2.y] = 1;
		}
		
	}
	return cnt;
}
 
int main()
{
	while(cin>>n>>m>>x) {
		if (bfs() == 0) {
			cout<<"impossible"<<endl;
		} 
	}
}
*/

当然，这道题目还见到有用其他方法去配合bfs进行解题的，

其他方法之一