BFS之喝可乐问题(C语言实现)

问题描述

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
Input
三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。
Output
如果能平分的话请输出最少要倒的次数，否则输出"NO"。
Sample Input
7 4 3
4 1 3
0 0 0
Sample Output
NO
3

• BFS的概念:宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

---

BFS每遍历一个结点都要进行标记，防止多次重复遍历，造成资源和时间上的浪费，还有可能导致死循环。

---

思路

• 首先，题目要求是所需次数最少就可均分可乐。求最少的问题一般都可用广度搜索来求解（BFS）。BFS最主要的就是先将题目分析清楚，每一次可以产生多少种情况，（就像树一层有多少个叶子一样），要将所有的可能都遍历到，这样才能求得答案。

• 分析情形: 有三个杯子，S, M, N。 可以先分六种情况，S->M, M->S, S->N, N->S, M->N, N->M。就是两两之间都可以互相倒。我最开始也只想到了这六种情况，结果在写的时候发现了问题。

• 假设 S这时候有10ml， M 有0ml， N有0ml。（S杯子容量为10ml， M为2ml， N为8ml）
  我们就先看一种情况，S->M, 首先判断S中要有可乐，其次要判断M是否装满了可乐(装满了就不能在被倒可乐了)。首先我们假设的情况这些条件都满足，S可以倒给M， 那倒完之后每个杯子的情况我们就得分析出来。 M的容量只有2ml， 所以S只能向M倒入2ml的可乐。
  所以倒完之后杯子剩余的情况就为 S 8ml, M 2ml, N 0ml。(可以倒满的情形)

• 这个时候我们在假设一种情况 S 有 2ml， M有 2ml， N有 6ml （S容量为10， M为 2， N 为 8）
  这个时候我们来看 N往S中倒的情形， 首先满足我们之前限定的那两个条件（1就是N有可乐。2就是S杯子还未满）所以N可以往S中倒可乐， N只有6ml可乐， 而S中还有8ml的空位置，所以倒完后的情形就为 S 8ml， M 2ml， N 0ml。这个时候我们发现计算的时候不能按照第一次的情形计算倒完后的情形。这次的情况是倒不满的情形，倒不满证明N倒完所有可乐还没有将S倒满，那么N这个杯子的剩余情况就可以直接写0, 而S杯子被倒入可乐后有（S可乐之前剩余的量加上N可乐中所有的量）。

• 之前有6种可以倒入的方案，在加上每种倒可乐都要分析倒满和未倒满两种情况，所以总共要分析12种情况进行遍历。

分析完了我们就要上代码进行讲解了。

• 首先模拟队列并且创建我们所需要的标记

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct Time  
{
	int s;               //S杯子当前有多少可乐
	int m;               //m杯子当前有多少可乐
	int n;               //n杯子当前有多少可乐
	int step;            //记录倒的次数
	struct Time *next;   
}time;

struct dir            //我们所需要的标记，模拟三维数组（开销比三维数组小很多）
{
	int s[101];          
	int m[101];
	int n[101];
};
/*模拟入队列的情况*/
void push(time **rear, int s, int m, int n, int step)
{
	time *temp;
	temp = (time*)malloc(sizeof(time));
	temp->s = s;
	temp->m = m;
	temp->n = n;
	temp->step = step;
	(*rear)->next = temp;
	temp->next = NULL;
	(*rear) = temp;
	(*rear)->next == NULL;
}
/* 模拟出队列的情况 */
time * pop(time **head)
{
	time *temp;
	temp = *head;
	*head  = (*head)->next;
	return temp;
}

int main(void)
{
	int s, m, n;         //s,m, n杯子的容量
	scanf("%d%d%d", &s, &m, &n);
	int flag;  
	struct dir *symbal = (struct dir*)malloc(sizeof(struct dir));
	
	/*将我们的标记数组都初始化为0*/
	memset(symbal->s, 0, 101 * 4);
	memset(symbal->m, 0, 101 * 4);
	memset(symbal->n, 0, 101 * 4);
	
	/*bfs的实现*/
	while(s != 0 || m != 0 || n != 0)
	{
		time *head, *rear;
		head = rear = (time *)malloc(sizeof(time));
		
		/*初始化每个杯子中可乐含量的情况*/
		head->s = s;     
		head->m = 0;
		head->n = 0;
		
		head->step = 0;      //初始化步数为0
		head->next = NULL;
		time *p;
		while(head != NULL)
		{
			p = head;
			if((p->s == p->m && p-> n == 0) || (p->s == p->n && p->m == 0))//满足条件时退出循环
			{
				flag = 1;
				break;
			}
			if( !(symbal->s[p->s] == 1 && symbal->m[p->m] == 1 && symbal->n[p->n] == 1) ) //判断标记，确定不重复遍历
			{
				/*将遍历过得情况进行标记，防止重复遍历*/
				symbal->s[p->s] = 1;
				symbal->m[p->m] = 1;
				symbal->n[p->n] = 1;
				
				if(p->m != m && p->s > 0 && p->s + p->m >= m)
					push(&rear, p->s -m + p->m, m, p->n, p->step + 1);   //s倒m
				if(p->m != m && p->s > 0 && p->s + p->m < m)
					push(&rear, 0, p->s+p->m, p->n, p->step + 1);

				if(p->s != s && p->m > 0 && p->s + p-> m >= s)         //m倒s
					push(&rear, s, p->m -s + p->s, p->n, p->step + 1);
				if(p->s != s && p->m > 0 && p->s + p->m < s)
					push(&rear, p->m + p->s, 0, p->n, p->step + 1);

				if(p->n != n && p->s > 0 && p->s + p-> n >= n)         //s倒n
					push(&rear, p->s -n + p->n, p->m, n, p->step + 1);
				if(p->n != n && p->s > 0 && p->s + p-> n < n)
					push(&rear, 0, p->m, p->s + p->n, p->step + 1);

				if(p->s != s && p->n > 0 && p->s + p-> n >=s)         //n倒s
					push(&rear, s, p->m, p->n -s + p->s, p->step + 1);
				if(p->s != s && p->n > 0 && p->s + p->n < s)
					push(&rear, p->s + p-> n, p->m, 0, p->step + 1);

				if(p->n != n && p->m > 0 && p->m + p-> n >= n)        //m倒n
				push(&rear, p->s, p->m - n + p->n, n, p->step +1);
				if(p->n != n && p->m > 0 && p->m + p->n < n)
					push(&rear, p->s, 0, p->m + p->n, p->step + 1);

				if(p->m != m && p->n > 0 && p->n + p-> m >= m)         //n倒m
					push(&rear, p->s, m, p->n - m + p->m, p->step + 1);
				if(p->m != m && p->n > 0 && p->n + p->m < m)
					push(&rear, p->s, p->m + p->n, 0, p->step + 1);
			}
			time *t = pop(&head); //释放队列中走过的结点
			free(t);
		}
		if(flag == 1)
			printf("%d\n", p->step);
		else
			printf("NO\n");
		while(head != NULL) //清空队列
		{
			time *temp = pop(&head);
			free(temp);
		}
		
		/*每一种情况结束，将标记清0*/
		memset(symbal->s, 0, sizeof(symbal->s));
		memset(symbal->m, 0, sizeof(symbal->m));
		memset(symbal->n, 0, sizeof(symbal->n));
		
		flag = 0;
		scanf("%d%d%d", &s, &m, &n);
	}	
	return 0;
}