GitBook

这里写图片描述 这里写图片描述

看博客里面搜索分类下的题目也不是很多…… 为什么感觉做过好多搜索题了……-.-

这一题还是很简单的 (话说突然感觉这种搜索都不难 设置好条件之后就不用动脑子了)

首先若要可以倒可乐S&1==0也就是S应为偶数 然后当N==M时 很显然只需要一次 其余的进行搜索 终止条件是S里面有S/2的饮料 N M中较大的那个里有剩下的一半饮料

然后……搜索就好了 为了剪枝 建个数组记录下当前的状态是否已经搜索过

这代码的亮点我感觉还是 通过数组来保存数据 可以达到用循环来找寻的目的 而不用一个一个地写

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int rflag[105][105][105];
struct node {
	int x[3];
	int cnt;
} t;
int main() {
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);

	int l[3];
	while(scanf("%d %d %d",&l[0],&l[1],&l[2]),l[0]||l[1]||l[2]) {
		memset(rflag,0,sizeof(rflag));
		if(l[0]&1)
			printf("NO\n");
		else if(l[1]==l[2])
			printf("1\n");
		else {
			if(l[1]>l[2]) {
				int t=l[1];
				l[1]=l[2];
				l[2]=t;
			}
			queue<node>q;
			t.x[0]=l[0];
			t.x[1]=0;
			t.x[2]=0;
			t.cnt=0;
			q.push(t);
			bool flag=false;
			int res;
			while(!q.empty()) {
				t=q.front();
				if(rflag[t.x[0]][t.x[1]][t.x[2]]) {
					q.pop();
					continue;
				}
				rflag[t.x[0]][t.x[1]][t.x[2]]=1;
				if(t.x[0]==l[0]/2&&t.x[1]==0&&t.x[2]==l[0]/2) {
					flag=true;
					res=t.cnt;
					break;
				}
				for(int i=0; i<3; i++) {
					if(t.x[i]>0) {
						for(int j=0; j<3; j++) {
							if(i==j||t.x[j]==l[j])
								continue;
							node tq=t;
							if(t.x[i]+t.x[j]>l[j]) {
								tq.x[i]=t.x[i]+t.x[j]-l[j];
								tq.x[j]=l[j];
								tq.cnt=t.cnt+1;
								q.push(tq);
							} else {
								tq.x[i]=0;
								tq.x[j]=t.x[i]+t.x[j];
								tq.cnt=t.cnt+1;
								q.push(tq);
							}
						}
					}
				}
				q.pop();
			}
			if(flag)
				printf("%d\n",res);
			else
				printf("NO\n");
		}
	}
	return 0;
}

题目地址:【杭电】[1495]非常可乐