首页 > 搜索 > BFS搜索 > hdu 2405 Marbles in Three Baskets-BFS-[解题报告]C++
2014
01-26

hdu 2405 Marbles in Three Baskets-BFS-[解题报告]C++

Marbles in Three Baskets

问题描述 :

Each of three baskets contains a certain number of marbles. You may move from one basket into another basket as many marbles as are already there, thus doubling the quantity in the basket that received the marbles. You must find a sequence of moves that will yield the same number of marbles in the three baskets. Moreover, you must achieve the goal in the smallest possible number of moves. Your program must also recognize the case in which there is no such sequence of moves.

输入:

Each line of the input file will contain data for one instance of the problem: three positive integers, with one blank space separating adjacent integers. The three integers represent the initial numbers of marbles in the three baskets. The sum of the three integers will be at most 60.

输出:

Each line of the input file will contain data for one instance of the problem: three positive integers, with one blank space separating adjacent integers. The three integers represent the initial numbers of marbles in the three baskets. The sum of the three integers will be at most 60.

样例输入:

6 7 11
15 18 3
5 6 7

样例输出:

   6   7  11
   6  14   4
  12   8   4
   8   8   8
============
  15  18   3
  12  18   6
  12  12  12
============
   5   6   7
============

想法很简单:宽搜。

问题是:如果得不到结果,怎么终止?我的笨办法是,当ed超过一定数目,如990时,就判断无法得到。这样也能过……

#include "stdio.h"

typedef struct _Bskt{
	int a, b, c;
	int pre;
}Bskt, *pBskt;

Bskt bskt[1000];
int st, ed;

int BFS(int a, int b, int c){
	Bskt k;
	if(a == b && b == c) return -1;
	if((a+b+c)%3) return -1;
	bskt[0].a = a;
	bskt[0].b = b;
	bskt[0].c = c;
	bskt[0].pre = -1;
	st = 0; ed = 1;

	while(st<ed){
		if(ed>990) return -1;
		k = bskt[st];
		//a
		if(k.b>=k.a && !(k.a+k.a==a && k.b-k.a==b && k.c==c)){
			bskt[ed].a = k.a + k.a;
			bskt[ed].b = k.b - k.a;
			bskt[ed].c = k.c;
			bskt[ed].pre = st;
			if(bskt[ed].a == bskt[ed].b && bskt[ed].b == bskt[ed].c) return ed;	
			ed++;
		}
		if(k.c>=k.a && !(k.a+k.a==a && k.b==b && k.c-k.a==c)){
			bskt[ed].a = k.a + k.a;
			bskt[ed].b = k.b;
			bskt[ed].c = k.c - k.a;
			bskt[ed].pre = st;
			if(bskt[ed].a == bskt[ed].b && bskt[ed].b == bskt[ed].c) return ed;
			ed++;
		}
		//b
		if(k.a>=k.b && !(k.a-k.b==a && k.b+k.b==b && k.c==c)){
			bskt[ed].a = k.a - k.b;
			bskt[ed].b = k.b + k.b;
			bskt[ed].c = k.c;
			bskt[ed].pre = st;
			if(bskt[ed].a == bskt[ed].b && bskt[ed].b == bskt[ed].c) return ed;
			ed++;
		}
		if(k.c>=k.b && !(k.a==a && k.b+k.b==b && k.c-k.b==c)){
			bskt[ed].a = k.a;
			bskt[ed].b = k.b + k.b;
			bskt[ed].c = k.c - k.b;
			bskt[ed].pre = st;
			if(bskt[ed].a == bskt[ed].b && bskt[ed].b == bskt[ed].c) return ed;
			ed++;
		}
		//c
		if(k.a>=k.c && !(k.a-k.c==a && k.b==b && k.c+k.c==c)){
			bskt[ed].a = k.a - k.c;
			bskt[ed].b = k.b;
			bskt[ed].c = k.c + k.c;
			bskt[ed].pre = st;
			if(bskt[ed].a == bskt[ed].b && bskt[ed].b == bskt[ed].c) return ed;
			ed++;
		}
		if(k.b>=k.c && !(k.a==a && k.b-k.c==b && k.c+k.c==c)){
			bskt[ed].a = k.a;
			bskt[ed].b = k.b - k.c;
			bskt[ed].c = k.c + k.c;
			bskt[ed].pre = st;
			if(bskt[ed].a == bskt[ed].b && bskt[ed].b == bskt[ed].c) return ed;
			ed++;
		}
		st++;
	}

	return -1;
}

void display(int pre){
	if(pre==-1)
		return;
	display(bskt[pre].pre);
	printf("%4d %3d %3d\n", bskt[pre].a, bskt[pre].b, bskt[pre].c);
}

void main(){
	int a, b, c, k;
	freopen("in.txt", "r", stdin);
	while(scanf("%d %d %d", &a, &b, &c)!=EOF){
		if((k=BFS(a, b, c))>=0)
			display(k);
		else
			printf("%4d %3d %3d\n", a, b, c);
		printf("============\n");
	}
}

解题转自:http://blog.csdn.net/chaoojie/article/details/7674029


,
  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法