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

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,并输出倒水的过程。

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

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

#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;

抱歉!评论已关闭.