2014
01-26

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

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
============

#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");
}
}

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