poj 3414 bfs+模拟

背景：1_WA:尽然忘了输出序列长度！！！我是怎么看的样例输出！！！改了之后ac!!这个题是很考代码能力的。

我的思路：就是6个出口的bfs，初始时候的两个容器的容量都是0，然后分别执行6个操作衍生出下一层（这里注意剪枝，比如第一个瓶子容量已经为0就没有必要再drop(1)了。这里很巧妙的是用了一个vis[iv][jv]数组来做访问标记，如果没有这个访问标记，后代呈现6的指数增长想必爆队列是必然的。还有巧妙的是自己YY一个diagram[iv][jv]来记录当前位置的上一个位置和由上一个位置走到当前位置的方法,实际想想这和普通bfs的路径标记似乎有异曲同工之妙处,只不过普通的bfs上一个路径是由方向数组计算出来的,而这个是直接记录。还有巧妙之处：路径记录是直到最后一个位置，这样倒退到起点如果直接输出的话操作序列是倒着的，我用了STL里的stack来讲顺序倒过来。

我的代码：

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define M 109
#define INF 0x3fffffff
#define LL long long int
using namespace std;
int iv,jv,ov,vis[M][M];
struct place{int i,j;}temp1,temp2;
struct maps{int last,x,y;}diagram[M][M];

bool bfs(void){
     queue<place> q;
     q.push(temp1);
     diagram[temp1.i][temp1.j].last=INF;// the over key.
     while(!q.empty()){
         temp1=q.front();
         q.pop();
         vis[temp1.i][temp1.j]=1;
         if(temp1.i == ov || temp1.j == ov){return true;}
         for(int k=0;k <  6;k++){
             if(k == 0 && temp1.i != iv){//把第一个瓶子装满。
                temp2.i=iv;
                temp2.j=temp1.j;
                if(!vis[temp2.i][temp2.j]){
                   q.push(temp2);
                   diagram[temp2.i][temp2.j].last=k;
                   diagram[temp2.i][temp2.j].x=temp1.i;
                   diagram[temp2.i][temp2.j].y=temp1.j;
                }
             }
             if(k == 1 && temp1.j != jv){
                temp2.i=temp1.i;
                temp2.j=jv;
                if(!vis[temp2.i][temp2.j]){//把瓶子2装满。
                   q.push(temp2);
                   diagram[temp2.i][temp2.j].last=k;
                   diagram[temp2.i][temp2.j].x=temp1.i;
                   diagram[temp2.i][temp2.j].y=temp1.j;
                }
             }
             if(k == 2 && temp1.i!= 0){//把瓶子1清空。
                temp2.i=0;
                temp2.j=temp1.j;
                if(!vis[temp2.i][temp2.j]){
                   q.push(temp2);
                   diagram[temp2.i][temp2.j].last=k;
                   diagram[temp2.i][temp2.j].x=temp1.i;
                   diagram[temp2.i][temp2.j].y=temp1.j;
                }
             }
             if(k == 3 && temp1.j != 0){//把瓶子2清空
                temp2.j=0;
                temp2.i=temp1.i;
                if(!vis[temp2.i][temp2.j]){
                   q.push(temp2);
                   diagram[temp2.i][temp2.j].last=k;
                   diagram[temp2.i][temp2.j].x=temp1.i;
                   diagram[temp2.i][temp2.j].y=temp1.j;
                }
             }
             if(k == 4 && temp1.i != 0 && temp1.j !=jv){//把瓶子1的水倒入瓶子2中。
                if(jv-temp1.j >= temp1.i){temp2.i=0;temp2.j=temp1.j+temp1.i;}
                else{temp2.i=temp1.i-(jv-temp1.j);temp2.j=jv;}
                if(!vis[temp2.i][temp2.j]){
                   q.push(temp2);
                   diagram[temp2.i][temp2.j].last=k;
                   diagram[temp2.i][temp2.j].x=temp1.i;
                   diagram[temp2.i][temp2.j].y=temp1.j;
                }
             }
             if(k == 5 && temp1.j != 0 && temp1.i !=iv){//把瓶子2的水倒入一中。
                if(iv-temp1.i >= temp1.j){temp2.j=0;temp2.i=temp1.i+temp1.j;}
                else{temp2.j=temp1.j-(iv-temp1.i);temp2.i=iv;}
                if(!vis[temp2.i][temp2.j]){
                   q.push(temp2);
                   diagram[temp2.i][temp2.j].last=k;
                   diagram[temp2.i][temp2.j].x=temp1.i;
                   diagram[temp2.i][temp2.j].y=temp1.j;
                }
             }
         }
     }
     return false;
}

void print(void){
     pair<int,int> pal1,pal2;
     stack<pair<int,int> > s;
     pal1.first=temp1.i;
     pal1.second=temp1.j;
     s.push(pal1);
     while(true){
        pal1=s.top();
        pal2.first=diagram[pal1.first][pal1.second].x;
        pal2.second=diagram[pal1.first][pal1.second].y;
        if(!pal2.first && !pal2.second) break;
        s.push(pal2);
     }
     printf("%d\n",s.size());
     while(!s.empty()){
        pal1=s.top();
        s.pop();
        int k=diagram[pal1.first][pal1.second].last;
        if(k == 0) printf("FILL(1)\n");
        else if(k == 1) printf("FILL(2)\n");
        else if(k == 2) printf("DROP(1)\n");
        else if(k == 3) printf("DROP(2)\n");
        else if(k == 4) printf("POUR(1,2)\n");
        else if(k == 5) printf("POUR(2,1)\n");
     }
}

int main(void){
    while(~scanf("%d%d%d",&iv,&jv,&ov)){
        memset(vis,0,sizeof(vis));//vis数组被看做字符串来优化的，只能用来初始化0之类的。
        temp1.i=0;
        temp1.j=0;//起始时刻两个容器里面都没有东西。
        if(bfs()) print();
        else printf("impossible\n");
    }
    return 0;
}

poj 3414 bfs+模拟

原文：http://blog.csdn.net/jibancanyang/article/details/44590445