| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
BFS 16ms。。。附代码,有详细备注!!!!!!!!!!!!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator