NYOJ-21 三个水杯 AC 分类： NYOJ 2014-02-08 11:35 174人阅读 评论(0) 收藏

人生中第一个AC的广搜题目，喵呜，C++的STL果真不错，

#include<stdio.h>
#include<queue>
#include<string.h> 
#include<windows.h>
using namespace std;
bool visited[100][100][100];  
int a, b, c;
struct Node{
	int a;
	int b;
	int c;
	int s;
};
	Node water;
	Node cup;
	Node fish;
	Node dream;
Node gb(Node key, int n){
	switch(n){
		case 0:
			key.b+=key.a;
			if(key.b>water.b){
				key.a=key.b-water.b;
				key.b=water.b;
			}
			else{
				key.a = 0;
			}
			break;
		case 1:
			key.c+=key.a;
			if(key.c>water.c){
				key.a=key.c-water.c;
				key.c=water.c;
			}
			else{
				key.a = 0;
			}
			break;
		case 2:
			key.c+=key.b;
			if(key.c>water.c){
				key.b=key.c-water.c;
				key.c=water.c;
			}
			else{
				key.b = 0;
			}
			break;
		case 3:
			key.a+=key.c;
			if(key.a>water.a){
				key.c=key.a-water.a;
				key.a=water.a;
			}
			else {
				key.c = 0;
			}
			break;
		case 4:
			key.a+=key.b;
			if(key.a>water.a){
				key.b=key.a-water.a;
				key.a=water.a;
			}
			else{
				key.b = 0;
			}
			break;
		case 5:
			key.b+=key.c;
			if(key.b>water.b){
				key.c=key.b-water.b;
				key.b=water.b;
			}
			else{
				key.c = 0;
			}
			break;
	}
	return key;
}
int main(){
	int i, sum, n;
	scanf("%d",&n);
	while(n--){
	
	queue<Node>num;
	
	scanf("%d%d%d",&water.a,&water.b,&water.c);
	scanf("%d%d%d",&fish.a,&fish.b,&fish.c);
	memset(visited, false, sizeof(visited));  
	cup.a = water.a;
	cup.b=0;
	cup.c=0;
	cup.s=0;
	visited[cup.a][0][0] = true;
	num.push(cup);
		while(!num.empty()){
			cup=num.front();
			if((cup.a==fish.a)&&(cup.b==fish.b))	break;
			for(i=0;i<6;i++){
				dream=gb(cup,i);
				dream.s++;
				if(visited[dream.a][dream.b][dream.c] == false){
					num.push(dream); 
					visited[dream.a][dream.b][dream.c] = true;
				}
			}
			num.pop();
		}
		if(num.empty()){
			printf("-1
");
		}else{
			printf("%d
",cup.s);
		}
		}
	return 0;
} 

若是对广搜的概念还是不懂的话，有道最好的入门题目，http://poj.org/problem?id=3278

大家加油