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+注释

Posted by 110120_119 at 2019-03-27 18:12:17 on Problem 3414
/*
每一个状态下,对应有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:
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