(step4.2.5)hdu 1495(非常可乐——BFS)

快来打我* 2021-12-13 14:47 200阅读 0赞

题目大意：输入三个整数 a,b,c.   a : 可乐瓶的容量，b: 甲杯的容量 ，c: 乙杯的容量。问能否用这三个被来实现饮料的平分？？？如果可以输出倒饮料的次数,

否则输出NO

解题思路:BFS

1）本题的考点其实在于将标记数组由二维数组变为三维数组。遍历状态由使用for()循环变为手动枚举，一个一个的if()

代码如下:

/*
     * 1495_2.cpp
     *
     *  Created on: 2013年8月16日
     *      Author: Administrator
     */
    
    #include <iostream>
    #include <queue>
    
    using namespace std;
    const int maxn = 102;
    bool visited[maxn][maxn][maxn];
    
    int a, b, c;
    struct State {
    	int a;
    	int b;
    	int c;
    	int v;
    };
    
    bool checkState(State st) {
    	if (!visited[st.a][st.b][st.c]) {
    		return true;
    	}
    
    	return false;
    }
    
    void bfs() {
    	queue<State> q;
    	State st, now, next;
    
    	st.a = a;
    	st.b = 0;
    	st.c = 0;
    	st.v = 0;
    	q.push(st);
    	memset(visited,0,sizeof(visited) );
    	visited[st.a][st.b][st.c] = 1;
    	while (!q.empty()) {
    		now = q.front();
    
    		//有2个等于a/2就结束
    		if ((now.a == a / 2 && now.b == a / 2)
    				|| (now.a == a / 2 && now.c == a / 2)
    				|| (now.c == a / 2 && now.b == a / 2)) {
    			printf("%d\n", now.v);
    			return ;
    		}
    
    		/**
    		 * 若a杯中的饮料的体积不为0,
    		 * 则枚举出将a杯中的饮料倒到其他杯中....
    		 */
    		if (now.a != 0) {
    			/**
    			 * 关键举得理解:now.a > b - now.b
    			 * now.a : now状态下a杯中的饮料的体积
    			 * b : b杯的体积
    			 * now.b :now状态下b杯中的饮料的体积
    			 *
    			 */
    			if (now.a > b - now.b) {//now.a > b - now.b。且倒不完
    				next.a = now.a - (b - now.b);
    				next.b = b;
    				next.c = now.c;
    				next.v = now.v + 1;
    			} else {//倒完了
    				next.a = 0;
    				next.b = now.b + now.a;
    				next.c = now.c;
    				next.v = now.v + 1;
    			}
    
    			if (checkState(next)) {
    				q.push(next);
    				visited[next.a][next.b][next.c] = 1;
    			}
    
    			if (now.a > c - now.c) {
    				next.a = now.a - (c - now.c);
    				next.b = now.b;
    				next.c = c;
    				next.v = now.v + 1;
    			} else {
    				next.a = 0;
    				next.b = now.b;
    				next.c = now.c + now.a;
    				next.v = now.v + 1;
    			}
    
    			if (checkState(next)) {
    				q.push(next);
    				visited[next.a][next.b][next.c] = 1;
    			}
    		}
    
    		if (now.b != 0) {
    			if (now.b > a - now.a) {
    				next.a = a;
    				next.b = now.b - (a - now.a);
    				next.c = now.c;
    				next.v = now.v + 1;
    			} else {
    				next.a = now.a + now.b;
    				next.b = 0;
    				next.c = now.c;
    				next.v = now.v + 1;
    			}
    
    			if (checkState(next)) {
    				q.push(next);
    				visited[next.a][next.b][next.c] = 1;
    			}
    
    			if (now.b > c - now.c) {
    				next.a = now.a ;
    				next.b = now.b - (c - now.c);
    				next.c = c;
    				next.v = now.v + 1;
    			} else {
    				next.a = now.a;
    				next.b = 0;
    				next.c = now.c + now.b;
    				next.v = now.v + 1;
    			}
    
    			if (checkState(next)) {
    				q.push(next);
    				visited[next.a][next.b][next.c] = 1;
    			}
    		}
    
    		if (now.c != 0) {
    			if (now.c > b - now.b) {
    				next.a = now.a ;
    				next.b = b;
    				next.c = now.c - (b - now.b);
    				next.v = now.v + 1;
    			} else {
    				next.a = now.a;
    				next.b = now.b + now.c;
    				next.c = 0;
    				next.v = now.v + 1;
    			}
    
    			if (checkState(next)) {
    				q.push(next);
    				visited[next.a][next.b][next.c] = 1;
    			}
    
    			if (now.c > a - now.a) {
    				next.a = a;
    				next.b = now.b;
    				next.c = now.c - (a - now.a);
    				next.v = now.v + 1;
    			} else {
    				next.a = now.a + now.c;
    				next.b = now.b;
    				next.c = 0;
    				next.v = now.v + 1;
    			}
    
    			if (checkState(next)) {
    				q.push(next);
    				visited[next.a][next.b][next.c] = 1;
    			}
    		}
    		q.pop();
    	}
    
    	printf("NO\n");
    }
    int main() {
    
    	while(scanf("%d%d%d",&a,&b,&c)!=EOF,a+b+c){
    		if(a%2 == 1){
    			printf("NO\n");
    		}else{
    			bfs();
    		}
    	}
    }

转载于:https://www.cnblogs.com/james1207/p/3262733.html