非常可樂

題目描述

大家一定覺得運動以後喝可樂是一件很愜意的事情，但是seeyou卻不這麼認為。因為每次當seeyou買了可樂以後，阿牛就要求和seeyou一起分享這一瓶可樂，而且一定要喝的和seeyou一樣多。但seeyou的手中只有兩個杯子，它們的容量分別是N 毫升和M 毫升 可樂的體積為\(S （S < 101）\)
毫升　(正好裝滿一瓶) ，它們三個之間可以相互倒可樂 (都是沒有刻度的，且\(S==N+M，101＞S＞0，N＞0，M＞0\)) 。聰明的OIER你們說他們能平分嗎？如果能請輸出倒可樂的最少的次數，如果不能輸出"NO"。

輸入

三個整數 : S 可樂的體積 , N 和 M是兩個杯子的容量，以"0 0 0"結束。

輸出

如果能平分的話請輸出最少要倒的次數，否則輸出"NO"。

樣例輸入

7 4 3
4 1 3
0 0 0

樣例輸出

NO
3

代碼

（不得不說好難啊）

#include <bits/stdc++.h>
using namespace std;
int vis[105][105][105];
int v[3];//可樂瓶和兩個杯子的容量
int s,n,m,flag;
struct node{
	int coke[3];//可樂瓶和兩個杯子當前的量
	int s;//倒的次數
};
void bfs()
{
	int avg=v[0]/2;
	memset(vis,0,sizeof(vis));
	flag=0;
	queue<node> q;
	node temp;
	
	temp.coke[0]=v[0];
	temp.coke[1]=0;
	temp.coke[2]=0;
	temp.s=0;
	
	vis[v[0]][0][0]=1;
	q.push(temp);
	while(!q.empty())
	{
		temp=q.front();
		q.pop();
		if((temp.coke[0]==avg&&temp.coke[1]==avg)||(temp.coke[0]==avg&&temp.coke[2]==avg)||(temp.coke[1]==avg&&temp.coke[2]==avg))
		{
			cout << temp.s << endl;
			flag=1;
			break;
		}
		//i杯子中的可樂往j中倒
		for(int i=0;i<3;i++)
		{//6種方案：0➡1  0➡2 1➡0 1➡2 2➡0 2➡1
			for(int j=0;j<3;j++)
			{
				if(i==j) continue;//自己不能給自己倒
				node tmp=temp;
				
				int pour=min(tmp.coke[i],v[j]-tmp.coke[j]);//取杯子i中的剩餘可樂和杯子j中的剩餘容量最小值
				tmp.coke[j]+=pour;
				tmp.coke[i]-=pour;
				
				if(!vis[tmp.coke[0]][tmp.coke[1]][tmp.coke[2]])
				{
					vis[tmp.coke[0]][tmp.coke[1]][tmp.coke[2]]=1;
					tmp.s++;
					q.push(tmp);
				}
			}
		}
	}
	if(!flag) cout << "NO\n";
}
int main()
{
	while(cin >> v[0] >> v[1] >> v[2]&&(v[0]||v[1]||v[2]))
	{
		if(v[0]%2==1)
		{
			cout << "NO\n";
			continue;
		}
		bfs();
	}
	return 0;
}

本文來自小默的博客，轉載請註明原文鏈接：https://www.cnblogs.com/momotrace/p/very-cola.html