(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()
コードは次のとおりです.
そうでなければ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();
}
}
}