现在的位置: 首页 > 综合 > 正文

poj 3414 dfs 广度优先搜索

2018年05月24日 ⁄ 综合 ⁄ 共 2436字 ⁄ 字号 评论关闭

题意:

给定两个杯子的容量a,b和目标水量c 。

有六种操作:

1、倒满a杯子。

? 2、倒满b杯子。

3、将a杯子的水全部倒出。?

4、将b杯子的水全部倒出。 ?

5、将a杯子的水倒到b杯子,直到a杯子倒尽或b杯子倒满。

6、将b杯子的水倒到a杯子,直到b杯子倒尽活a杯子倒满。

求:最少进行多少次操作使a或b任意一杯子的水量恰好等于目标水量c,并输出倒水的过程。

题目链接://poj.org/problem?id=3414

求解思路:6入口的BFS,记录每一次操作的前一次操作,当恰好找到目标状态的时候,从末尾找到初始状态输出。

 秒速赛车公式 www.l19l7.cn #include<stdio.h>
#include<cstring>
#include<iostream>
#include<cstring>
using namespace std;
struct State
{
    int post;
    int a,b;
    int step;
    char d[10];
}state[10010];
int haha[10010];
int A,B,C;
bool visit[105][105];//标记该状态时否被访问过
int BFS()
{
    int head=0,tail=0;
    visit[0][0]=true;
    state[tail].a=0;
    state[tail].b=0;
    state[tail].step=0;
    state[tail].post=-2;
    tail++;
    while(1)
    {
        State x=state[head];
        //cout<<state[head].a<<"*"<<state[head].b<<endl;
        if(head==tail)
        {
           return -1;//队列为空,找不到.
        }

        if(x.a==C||x.b==C)
        {
            return head;
        }

        if(!visit[A][x.b])// fill A;
        {
            visit[A][x.b]=true;
            state[tail].b=x.b;//这地方不要忘了记录,wa了好久
            state[tail].a=A;
            state[tail].post=head;
            strcpy(state[tail].d,"FILL(1)");
            state[tail++].step=x.step+1;
        }
        if(!visit[x.a][B]) //fill B
        {
            visit[x.a][B]=true;
            state[tail].a=x.a;
            state[tail].b=B;
            state[tail].post=head;
            strcpy(state[tail].d,"FILL(2)");
            state[tail++].step=x.step+1;
        }


        if(x.a+x.b<=B)    //pour(a,b)
        {
            if(!visit[0][x.a+x.b])
            {
                visit[0][x.a+x.b]=true;
                state[tail].b=x.a+x.b;
                state[tail].a=0;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(1,2)");
                state[tail++].step=x.step+1;
            }
        }
        else
        {
            if(!visit[x.a-(B-x.b)][B])
            {
                visit[x.a-(B-x.b)][B]=true;
                state[tail].a=x.a-(B-x.b);
                state[tail].b=B;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(1,2)");
                state[tail++].step=x.step+1;
            }
        }

        if(x.b+x.a<=A)   //pour(b,a);
        {
            if(!visit[x.a+x.b][0])
            {
                visit[x.a+x.b][0]=true;
                state[tail].a=x.a+x.b;
                state[tail].step=x.step+1;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(2,1)");
                state[tail++].b=0;
            }
        }
        else
        {
            if(!visit[A][x.b-(A-x.a)])
            {
                visit[A][x.b-(A-x.a)]=true;
                state[tail].b=x.b-(A-x.a);
                state[tail].a=A;
                state[tail].post=head;
                strcpy(state[tail].d,"POUR(2,1)");
                state[tail++].step=x.step+1;
            }
        }

         if(!visit[0][x.b]) //drop A
        {
            visit[0][x.b]=true;
            state[tail].a=0;
            state[tail].b=x.b;
            state[tail].post=head;
            strcpy(state[tail].d,"DROP(1)");
            state[tail++].step=x.step+1;
        }
        if(!visit[x.a][0]) //drop B
        {
            visit[x.a][0]=true;
            state[tail].b=0;
            state[tail].a=x.a;
            state[tail].post=head;
            strcpy(state[tail].d,"DROP(2)");
            state[tail++].step=x.step+1;
        }
        head++;
    }
}
int main()
{
    while(scanf("%d%d%d",&A,&B,&C)!=EOF)
    {
        memset(visit,false,sizeof(visit));
        int t=BFS();
        if(t==-1)
        printf("impossible\n");
        else
        {
            int i=0;
            while(state[t].post!=-2)
            {

                haha[i]=t;
                i++;
                t=state[t].post;
            }
            cout<<i<<endl;
            for(int j=i-1;j>=0;j--)
            {
                cout<<state[haha[j]].d<<endl;
            }
        }
    }
    return 0;

抱歉!评论已关闭.

  • 听,盲童唱出心底的阳光 2018-12-17
  • 老婆告老公索债780万 原是二人自导自演 2018-12-17
  • 井冈山交警开展重点车辆严重交通违法行为有奖举报工作 2018-12-17
  • 停车收费新政首日举报量攀升 2018-12-17
  • 这是世界杯开赛当晚的广西 2018-12-16
  • 【理上网来·喜迎十九大】建设世界一流军队的科学指南 2018-12-16
  • 第六届北京农业嘉年华--北京频道--人民网 2018-12-16
  • 【专题】节能降耗 保卫蓝天——浙江省暨杭州市2018年节能宣传周 2018-12-15
  • 【奋斗在新时代】劳道“歹猫”增色互联网“表情” 2018-12-15
  • 驾车撞倒城管队员反复碾压 义乌暴力摊贩被刑拘 2018-12-15
  • 《中国汽车报》2018“西部温暖计划”公益试驾活动即将启程 2018-12-14
  • 奇瑞新能源瑞虎3xe上市 售价8.98万 2018-12-14
  • 几家性价比超高的烤肉店 赶紧去试试 2018-12-14
  • 和“看着就想笑”说说你的“8421” 2018-12-13
  • 中共十八大以来藏语新词术语发布 2018-12-13
  • 368| 490| 496| 209| 452| 991| 790| 208| 963| 455|