H - Pots POJ 3414 算是小白书所讲的一般隐式图搜索， BFS

POUR(2,1)

//刘汝佳的小白书里，只是提到过一个概念，叫做隐式图搜索，个人觉得，就是搜索的，不是常见的矩阵或者邻接表存储的图，而是比较抽象的图，以本题为例，状态可以理解为图的节点，由这个状态能到另一个状态就是表明这两个状态之间是有边的 ，那么就可以以图的搜索思路来写了，本题的状态是两个杯子的水量，比如初始没有水，那就是（0,0），但是有三种操作，所以由（0,0）可以到（A，0）,(0,B)...等

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
using namespace std;
const int maxn=50005;
const int inf=200000;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r

template<class T>inline T read(T&x)
{
    char c;
    while((c=getchar())<=32);
    bool ok=false;
    if(c=='-')ok=true,c=getchar();
    for(x=0; c>32; c=getchar())
        x=x*10+c-'0';
    if(ok)x=-x;
    return x;
}
template<class T> inline void read_(T&x,T&y)
{
    read(x);
    read(y);
}
template<class T> inline void write(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{
    write(x);
    putchar('\n');
}
//  -------IO template------
int A,B,C;
struct node
{
    int a,b;
    int id;
    node(int x,int y,int d){id=d;a=x;b=y;}
};
bool vis[105][105];
int num=0;
int d[maxn];
int p[maxn];
bool ok;
map<int,string> mp;
map<int,string>::iterator it;

void bfs(node s)
{
    queue<node> q;
    q.push(s);
    memset(vis,false,sizeof(vis));
    memset(p,-1,sizeof(p));
    mp.clear();
    d[0]=0;
    p[0]=-1;
    vis[s.a][s.b]=true;
    num=1;
    while(!q.empty())
    {
        node s=q.front();q.pop();
        if(s.a==C||s.b==C)
        {
            printf("%d\n",d[s.id]);
            it=mp.begin();
            stack<string> ss;
            for(int i=s.id;i!=-1;i=p[i])
            {
               // printf("(%d)\n",i);
                it=mp.begin();
                while(it->first!=i&&it!=mp.end())
                {
                   it++;
                }
                ss.push(it->second);
            }
            ss.pop();
            while(!ss.empty())
            {
                printf("%s\n",ss.top().c_str());
                ss.pop();
            }
            ok=1;
            return;
        }
//bfs按层次搜索能到达的六条边

       if(s.a<A&&!vis[A][s.b])
        {
            vis[A][s.b]=true;
            q.push(node(A,s.b,num));
            d[num]=d[s.id]+1;
            mp[num]="FILL(1)";
            p[num++]=s.id;
        }
        if(s.b<B&&!vis[s.a][B])
        {
            vis[s.a][B]=true;
            q.push(node(s.a,B,num));
            d[num]=d[s.id]+1;
            mp[num]="FILL(2)";
            p[num++]=s.id;
        }
        if(s.a>0&&!vis[0][s.b])
        {
            vis[0][s.b]=true;
            q.push(node(0,s.b,num));
            d[num]=d[s.id]+1;
            mp[num]="DROP(1)";
            p[num++]=s.id;
        }
        if(s.b>0&&!vis[s.a][0])
        {
            vis[s.a][0]=true;
            q.push(node(s.a,0,num));
            d[num]=d[s.id]+1;
            mp[num]="DROP(2)";
            p[num++]=s.id;
        }
        if(s.a>0&&s.b<B)
        {
            int t=min(s.a,B-s.b);
            if(!vis[s.a-t][s.b+t])
            {
                vis[s.a-t][s.b+t]=true;
                q.push(node(s.a-t,s.b+t,num));
                d[num]=d[s.id]+1;
                mp[num]="POUR(1,2)";
                p[num++]=s.id;
            }
        }
        if(s.a<A&&s.b>0)
        {
            int t=min(s.b,A-s.a);
            if(!vis[s.a+t][s.b-t])
            {
                vis[s.a+t][s.b-t]=true;
                q.push(node(s.a+t,s.b-t,num));
                d[num]=d[s.id]+1;
                mp[num]="POUR(2,1)";
                p[num++]=s.id;
            }
        }
    }
}
int main()
{
    int n,m,i,j,k,t;
   // freopen("in.txt","r",stdin);
    read(A);
    read(B);
    read(C);
    ok=0;
    bfs(node(0,0,0));
    if(!ok)printf("impossible\n");
    return 0;
}

H - Pots POJ 3414 算是小白书所讲的一般隐式图搜索， BFS

原文：http://blog.csdn.net/u013167299/article/details/44543107