Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

BFS 16ms。。。附代码,有详细备注!!!!!!!!!!!!

Posted by 448501561 at 2014-07-18 21:41:33 on Problem 3414
#include<iostream>
#include<cstring>
using namespace std;

struct AB
{
    int pre;//指向前一状态(前一状态数组下标)
    int a,b;
    int c;//通过第几个操作得到当前状态
};
AB q[10050];//存储状态
int head,tail;
int A,B,C;
int aa,bb;//当前两桶里的水
bool visit[101][101];//A,B<=100,所以有100*100种状态,判断此状态是否访问过。

void FILL(int i)
{
    if(i==1)
        aa=A;
    else bb=B;
}

void POUR(int i,int j)
{
    int a=aa,b=bb;
    if(i==1)
    {
        if(a+b>B)
        {
            bb=B;
            aa=a+b-B;
        }
        else
        {
            bb=a+b;
            aa=0;
        }
    }
    else
    {
        if(a+b>A)
        {
            aa=A;
            bb=a+b-A;
        }
        else
        {
            aa=a+b;
            bb=0;
        }
    }
}

void DROP(int i)
{
    if(i==1)
        aa=0;
    else bb=0;
}

void operate(int i)
{
    switch(i)
    {
    case 0:
    {
        FILL(1);
        break;
    }
    case 1:
    {
        FILL(2);
        break;
    }
    case 2:
    {
        POUR(1,2);
        break;
    }
    case 3:
    {
        POUR(2,1);
        break;
    }
    case 4:
    {
        DROP(1);
        break;
    }
    case 5:
    {
        DROP(2);
        break;
    }
    }
}

void out(int i)
{
    switch(i)
    {
    case 0:
    {
        cout<<"FILL(1)"<<endl;
        break;
    }
    case 1:
    {
        cout<<"FILL(2)"<<endl;
        break;
    }
    case 2:
    {
        cout<<"POUR(1,2)"<<endl;
        break;
    }
    case 3:
    {
        cout<<"POUR(2,1)"<<endl;
        break;
    }
    case 4:
    {
        cout<<"DROP(1)"<<endl;
        break;
    }
    case 5:
    {
        cout<<"DROP(2)"<<endl;
        break;
    }
    }
}

int BFS()
{
    head=tail=0;
    q[tail].a=0;
    q[tail].b=0;
    q[tail++].pre=-1;//标记该状态为起始点
    visit[0][0]=true;
    while(true)
    {
        if(head==tail)
        {
            return 0;//队列为空,未找到目标状态,无解
        }
        if(q[head].a==C||q[head].b==C)
        {
            return head;//返回目标状态下标
        }
        for(int i=0; i<6; i++)
        {
            aa=q[head].a;
            bb=q[head].b;//读取当前状态
            operate(i);//计算操作i之后的状态
            if(!visit[aa][bb])//如果此状态未访问
            {
                visit[aa][bb]=true;
                q[tail].pre=head;//由当前状态产生的状态,所以pre指向当前状态
                q[tail].a=aa;
                q[tail].b=bb;
                q[tail++].c=i;//记录操作i
            }
        }
        head++;
    }
}

int main()
{
    cin>>A>>B>>C;
    memset(visit,false,sizeof(visit));
    int t=BFS();
    int way[10000],n=0;
    if(!t)
        cout<<"impossible"<<endl;
    else
    {
        while(q[t].pre!=-1)//统计到达目标状态所经过状态个数(初始状态不算)并记录状态下标
        {                  //状态数组中只有指向前一状态,无法正向输出,将状态下标记录到way[]中进行倒序输出;
            way[n++]=t;
            t=q[t].pre;
        }
        cout<<n<<endl;
        while(n--)
        {
            out(q[way[n]].c);
        }
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator