| ||||||||||
| 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+注释/*
每一个状态下,对应有6种操作
1,fill A
2,fill B
3,drop A
4,drop B
5,pour A-->B 此时有两种可能
5-1,A可以全部倒入B中 A中剩余0,B中剩余A+B
5-2,A不可以全部倒入B中 A中剩余A+B-b ,B中满
6,pour B-->A 此时和5一样,同样有两种可能
*/
#include<cstdio>
#pragma warning (disable:4996)
using namespace std;
const int MAX = 110;
int a, b, c; //记录两个容器的大小及最终目标
int step; //最终的步数
bool flag; //能否找到最终状态的标志
int lastIndex; //标记符合条件的状态在队列中的位置
int visit[MAX][MAX]; //状态数组,若是相同的状态,则不需要再加入队列
struct Status
{
int k1, k2;
int step;
int op; //操作的方法
int fatherPosition; //上一个状态在队列中的位置,方便找到上一个状态,这样就可以获取上一个状态操作的方法
}queue[MAX*MAX];
void bfs()
{
Status now, next; //当前状态,下一个状态
int head=0, tail=1; //头指针、尾指针
now.k1 = 0; now.k2 = 0; now.op = 0; now.step = 0; now.fatherPosition = 0; //将当前状态设置成初始状态
queue[0] = now; //当前状态入队
visit[0][0] = 1;
while (head < tail) //只要队列不空,则继续入队、出队操作
{
//头指针所指的出队,出队的状态为当前状态
now = queue[head];
head++; //出队后,头指针往后移动一个
//对于当前的状态,让所有可能的下一个状态入队,一个状态的所有可能的下一个状态共有6种
for (int i = 1; i <= 6; i++)
{
switch (i)
{
case 1: //fill(a)
next.k1 = a;
next.k2 = now.k2;
break;
case 2: //fill(b)
next.k1 = now.k1;
next.k2 = b;
break;
case 3: //drop(a)
next.k1 = 0;
next.k2 = now.k2;
break;
case 4: //drop(b)
next.k1 = now.k1;
next.k2 = 0;
break;
case 5: //pour(a, b) a--->b
if ((now.k1 + now.k2) <= b)
{
next.k1 = 0;
next.k2 = now.k1 + now.k2;
}
else
{
next.k1 = (now.k1 + now.k2) - b;
next.k2 = b;
}
break;
case 6: //pour(b,a) b--->a
if ((now.k1 + now.k2) <= a)
{
next.k1 = now.k1 + now.k2;
next.k2 = 0;
}
else
{
next.k1 = a;
next.k2 = (now.k1 + now.k2) - a;
}
break;
}
next.op = i; //记录下一个状态的操作
//printf("head=%d tail=%d i=%d (%d,%d)\n", head, tail, i, next.k1, next.k2); //判断头、尾指针以及入队出队是否正确
if (!visit[next.k1][next.k2]) //如果下一个状态未曾被加入到队列中
{
//printf("****\n"); //判断是否入队
visit[next.k1][next.k2] = 1; //标记
next.step = now.step + 1; //将该状态的步数加1
next.fatherPosition = head - 1; //它爸爸就是当前状态(刚出队的),因为出队后头指针往后移动了一个,所以这个减一,表示它爸在队列中的位置
queue[tail] = next; //将下一个状态加入队列尾部,有状态入队后,尾指针往后移动一个
tail++;
//判断这个状态是否是最终状态,若是,直接结束了,若不是,加入队列
if (next.k1 == c || next.k2 == c)
{
flag = true; //标志位置真
step = next.step; //更新最终步数
lastIndex = tail - 1; //若这个状态是最终状态,则将这个状态在队列中的位置标记一下
return; //找到后,直接退出bfs
}
}
}
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt","w",stdout);
while (scanf("%d %d %d", &a, &b, &c) != EOF)
{
step = 0;
flag = false;
int id[MAX*MAX]; //记录到达最终状态过程中,每一个状态在队列中的位置
for (int i = 0; i < MAX; i++) //状态数组清零
for (int j = 0; j < MAX; j++)
visit[i][j] = 0;
//printf("!!!!!\n");
bfs();
//printf("!!!!!\n");
if (flag)
{
printf("%d\n", step);
//最后一个状态在队列中的下标是lastIndex
id[step] = lastIndex;
for (int i = step - 1; i >= 1; i--) //通过fatherPosition参数从最后一个状态开始往前找它的父状态,并且记录每个状态的操作
{
id[i] = queue[id[i + 1]].fatherPosition; //id[i+1]表示后一个状态在队列中的下标
}
for (int i = 1; i <= step; i++)
{
switch (queue[id[i]].op) //所有有效的状态的操作
{
case 1:
printf("FILL(1)\n");
break;
case 2:
printf("FILL(2)\n");
break;
case 3:
printf("DROP(1)\n");
break;
case 4:
printf("DROP(2)\n");
break;
case 5:
printf("POUR(1,2)\n");
break;
case 6:
printf("POUR(2,1)\n");
break;
}
}
}
else
printf("impossible\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator