NYOJ 21コップ3個(BFS)
3748 ワード
タイトルリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=21
コップ3杯
時間制限:
1000 ms | メモリの制限:
65535 KB
難易度:
4
説明
3つのコップが与えられ、大きさが異なり、最大のコップの水だけがいっぱいで、残りの2つは空のコップです.3つのコップの間は互いに水を注ぎ合い、コップには標識がなく、与えられたコップの体積に基づいて計算するしかない.初期状態をターゲット状態に到達させる最小回数を出力するプログラムを書く必要があります.
入力
1行目の整数N(0次に、各試験データのセットは2行あり、第1行は、3つのコップの体積を表す3つの整数V 1 V 2 V 3(V 1>V 2>V 3<100 V 3>0)を与える.
2行目は3つの整数E 1 E 2 E 3(体積が対応するコップの体積以下)を与え、私たちが必要とする最終状態を表す.
しゅつりょく
各行は、対応するテストデータの最小の給水回数を出力します.目標状態に達しない場合出力-1
サンプル入力
サンプル出力
経典広捜題.
コードが醜い.の
コップ3杯
時間制限:
1000 ms | メモリの制限:
65535 KB
難易度:
4
説明
3つのコップが与えられ、大きさが異なり、最大のコップの水だけがいっぱいで、残りの2つは空のコップです.3つのコップの間は互いに水を注ぎ合い、コップには標識がなく、与えられたコップの体積に基づいて計算するしかない.初期状態をターゲット状態に到達させる最小回数を出力するプログラムを書く必要があります.
入力
1行目の整数N(0
2行目は3つの整数E 1 E 2 E 3(体積が対応するコップの体積以下)を与え、私たちが必要とする最終状態を表す.
しゅつりょく
各行は、対応するテストデータの最小の給水回数を出力します.目標状態に達しない場合出力-1
サンプル入力
2
6 3 1
4 1 1
9 3 2
7 1 1サンプル出力
3
-1経典広捜題.
コードが醜い.の
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int A, B, C;
int EA, EB, EC;
struct node {
int a, b, c;
int cnt;
};
int vis[110][110][110];
void move(node& now, node& next, int c) {
if(c - now.b >= now.a) {
next.a = 0;
next.b = now.b + now.a;
}
else {
next.a = now.a - (c - now.b);
next.b = c;
}
next.cnt = now.cnt + 1;
}
int bfs() {
node now, next;
now.a = A, now.b = 0, now.c = 0, now.cnt = 0;
queue<node> q;
q.push(now);
int i;
vis[now.a][now.b][now.c] = 1;
while(!q.empty()) {
now = q.front();
q.pop();
if(now.a == EA && now.b == EB && now.c == EC) {
return now.cnt;
}
next = now;
if(now.a != 0 && now.b < B) {
if(B - now.b >= now.a) {
next.a = 0;
next.b = now.b + now.a;
}
else {
next.a = now.a - (B - now.b);
next.b = B;
}
next.cnt = now.cnt + 1;
if(!vis[next.a][next.b][next.c]) {
vis[next.a][next.b][next.c] = 1;
q.push(next);
}
}
next = now;
if(now.a != 0 && now.c < C) {
if(C - now.c >= now.a) {
next.a = 0;
next.c = now.c + now.a;
}
else {
next.a = now.a - (C - now.c);
next.c = C;
}
next.cnt = now.cnt + 1;
if(!vis[next.a][next.b][next.c]) {
vis[next.a][next.b][next.c] = 1;
q.push(next);
}
}
next = now;
if(now.b != 0 && now.a < A) {
if(A - now.a >= now.b) {
next.b = 0;
next.a = now.a + now.b;
}
else {
next.b = now.b - (A - now.a);
next.a = A;
}
next.cnt = now.cnt + 1;
if(!vis[next.a][next.b][next.c]) {
vis[next.a][next.b][next.c] = 1;
q.push(next);
}
}
next = now;
if(now.c != 0 && now.a < A) {
if(A - now.a >= now.c) {
next.c = 0;
next.a = now.a + now.c;
}
else {
next.c = now.c - (A - now.a);
next.a = A;
}
next.cnt = now.cnt + 1;
if(!vis[next.a][next.b][next.c]) {
vis[next.a][next.b][next.c] = 1;
q.push(next);
}
}
next = now;
if(now.b != 0 && now.c < C) {
if(C - now.c >= now.b) {
next.b = 0;
next.c = now.c + now.b;
}
else {
next.b = now.b - (C - now.c);
next.c = C;
}
next.cnt = now.cnt + 1;
if(!vis[next.a][next.b][next.c]) {
vis[next.a][next.b][next.c] = 1;
q.push(next);
}
}
next = now;
if(now.c != 0 && now.b < B) {
if(B - now.b >= now.c) {
next.c = 0;
next.b = now.b + now.c;
}
else {
next.c = now.c - (B - now.b);
next.b = B;
}
next.cnt = now.cnt + 1;
if(!vis[next.a][next.b][next.c]) {
vis[next.a][next.b][next.c] = 1;
q.push(next);
}
}
}
return -1;
}
int main() {
int N;
scanf("%d", &N);
while(N--) {
scanf("%d %d %d", &A, &B, &C);
scanf("%d %d %d", &EA, &EB, &EC);
memset(vis, 0, sizeof(vis));
printf("%d
", bfs());
}
return 0;
}