水の移し替えパズル
Posted feedbacks - Java
愚直に一リットルずつ動かして全可能性を網羅しています（ただし、往復の移動は避けています）。 4L, 2L, 10L の時は10でした。 827392L，65536L，122880Lのときはスタックが溢れて求められません。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | public class Sample {
private static int[] volume = {4, 2, 10};
private static boolean[] dFlag = new boolean[3];
private static int minStep = Integer.MAX_VALUE;
public static void move(int dest, int step) {
boolean so = dFlag[dest];
try {
volume[dest] += 2;
volume[(dest + 1) % 3]--;
volume[(dest + 2) % 3]--;
dFlag[dest] = true;
int emptyCount = 0;
int destCount = 0;
for (int i = 0; i < 3; i++) {
if (volume[i] < 0) {
return;
} else if (volume[i] == 0) {
emptyCount++;
}
if (dFlag[i]) destCount++;
}
if (destCount == 3) return;
if (emptyCount == 2) {
if (minStep > step + 1)
minStep = step + 1;
} else {
move(0, step + 1);
move(1, step + 1);
move(2, step + 1);
}
} finally {
dFlag[dest] = so;
volume[dest] -= 2;
volume[(dest + 1) % 3]++;
volume[(dest + 2) % 3]++;
}
}
public static void main(String[] args) {
move(0, 0);
move(1, 0);
move(2, 0);
System.out.println(minStep);
}
}
|
にしお
#3547()
Rating0/2=0.00
A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている． ここで次の操作を繰り返す．
(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」
たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる． くみ上げる前の容器には必ず水が入っているとする．
(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．
可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．
このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。
[ reply ]