(step 4.2.5)hdu 1495(非常コーラ——BFS)

4441 ワード

3つの整数a,b,c.a:コーラ瓶の容量、b:甲杯の容量、c:乙杯の容量を入力します.この3つで飲み物の平分を実現できますか??飲み物を入れる回数を出力できれば、
そうでなければNOを出力する
解題構想:BFS
1)本題のポイントは,タグ配列を2次元配列から3次元配列に変更することである.遍歴状態はfor()ループの使用から手動列挙に変わり,1つ1つ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
", 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
"); } int main() { while(scanf("%d%d%d",&a,&b,&c)!=EOF,a+b+c){ if(a%2 == 1){ printf("NO
"); }else{ bfs(); } } }