倒水问题（dp+bfs）
DP BFS 问题
2023-09-11 14:20:52 时间
1 问题描述
有A、B、C三个杯子，没有刻度，容量分别为A、B、C，只使用这三个杯子，如何量出容量为K的水？
要求：水可以无限用，每个杯子的水可以倒掉，也可以重新装满，还可以倒进别的杯子。
2 状态分析
以每个杯子的水的盛水量为状态，即状态节点使用三元组（a，b，c）表示，一共有(A+1)*(B+1)*(C+1)种状态。若由T1状态经一步倒水操作可达到T2状态，则T1到T2间有一条边，记为T1->T2，由此可建立一个有向图。
对于每个状态，最多有如下12条状态转移规则：
- 若a>0 ==> a=0；（若A杯有水，倒掉A杯水）
- 若b>0 ==> b=0；（若B杯有水，倒掉B杯水）
- 若c>0 ==> c=0；（若C杯有水，倒掉C杯水）
- 若a<A ==> a=A；（若A杯未满，倒满A杯水）
- 若b<B ==> b=B；（若B杯未满，倒满B杯水）
- 若c<C ==> c=C；（若C杯未满，倒满C杯水）
- 若a<A && b>0 ==> 若b+a<=A，a=b+a, b=0 ；若b+a>A，b=b+a-A, a=A；（B->A）
- 若a<A && c>0 ==> 若c+a<=A，a=c+a, c=0 ；若c+a>A，c=c+a-A, a=A；（C->A）
- 若b<B && a>0 ==> 若a+b<=B，b=a+b, a=0 ；若a+b>B，a=a+b-B, b=B；（A->B）
- 若b<B && c>0 ==> 若c+b<=B，b=c+b, c=0 ；若c+b>B，c=c+b-B, b=B；（C->B）
- 若c<C && a>0 ==> 若a+c<=C，c=a+c, a=0；若a+c>C，a=a+c-C, c=C；（A->C）
- 若c<C && b>0 ==> 若b+c<=C，c=b+c, b=0；若b+c>C，b=b+c-C, c=C；（B->C）
3 算法分析
定义数组 dp[A+1][B+1][C+1] ，dp[i][j][k] 表示从状态（0, 0, 0）到状态（i, j, k）所需经过的步数，定义数组path[A+1][B+1][C+1] 表示从状态（0, 0, 0）到状态（i, j, k）在步数最少的情况下，前一状态信息。
使用广度优先搜索（BFS），每次状态步数有变动时，更新步数，并把当前状态添加到队列中，以便下次更新当前状态的下一个状态的步数。
核心代码：
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;
class Status{
int a;
int b;
int c;
Status(int a,int b,int c){
this.a=a;
this.b=b;
this.c=c;
}
}
public class Main {
static int A,B,C,K;
static int[][][] dp;
static int ans;
static final int MAX=10000000;
static Status[][][] path;
static LinkedList<Status> que=new LinkedList<Status>();
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
A=sc.nextInt();
B=sc.nextInt();
C=sc.nextInt();
K=sc.nextInt();
dp=new int[A+1][B+1][C+1];
path=new Status[A+1][B+1][C+1];
for(int i=0;i<=A;i++) {
for(int j=0;j<=B;j++) {
for(int k=0;k<=C;k++) {
dp[i][j][k]=MAX;
path[i][j][k]=new Status(0,0,0);
}
}
}
bfs(); //使用BFS填充dp表
Status status=choose(); //选择有一个杯子盛水量为K，且步数最少的状态
print(status); //打印路径及最小步数
}
static void bfs() { //使用BFS填充dp表
dp[0][0][0]=0;
path[0][0][0]=null;
que.add(new Status(0,0,0));
while(!que.isEmpty()) {
Status sta=que.remove(); //出队
int a=sta.a;
int b=sta.b;
int c=sta.c;
for(int i=0;i<12;i++) { //遍历12个孩子状态
Status s=change(a,b,c,i); //改变盛水量（从当前状态到下一个状态）
if(s!=null) {
que.add(s); //入队
}
}
}
}
}运行结果：
其他方法代码 ：
static Status choose() { //选择有一个杯子盛水量为K，且步数最少的状态
int a=0,b=0,c=0;
ans=MAX;
if(K<=C) {
for(int i=0;i<=A;i++) {
for(int j=0;j<=B;j++) {
if(dp[i][j][K]<ans) {
ans=dp[i][j][K];
a=i;
b=j;
c=K;
}
}
}
}
if(K<=B) {
for(int i=0;i<=A;i++) {
for(int k=0;k<=C;k++) {
if(dp[i][K][k]<ans) {
ans=dp[i][K][k];
a=i;
b=K;
c=k;
}
}
}
}
if(K<=A) {
for(int j=0;j<=B;j++) {
for(int k=0;k<=C;k++) {
if(dp[K][j][k]<ans) {
ans=dp[K][j][k];
a=K;
b=j;
c=k;
}
}
}
}
return new Status(a,b,c);
}
static void print(Status status) { //打印路径及最小步数
Stack<Status> stack=new Stack<Status>();
while(status!=null) {
stack.add(status);
int a=status.a;
int b=status.b;
int c=status.c;
status=path[a][b][c];
}
while(!stack.isEmpty()) {
status=stack.pop();
int a=status.a;
int b=status.b;
int c=status.c;
if(stack.size()>0)
System.out.print("("+a+","+b+","+c+")->");
else
System.out.print("("+a+","+b+","+c+")");
}
System.out.println("\n"+ans);
}
static Status change(int i,int j,int k,int s) { //改变盛水量（从当前状态到下一个状态）
Status sta=new Status(i,j,k);
switch(s) {
case 0: //倒空A杯水
if(i>0) {
if(dp[0][j][k]>dp[i][j][k]+1) {
dp[0][j][k]=dp[i][j][k]+1;
path[0][j][k]=sta;
return new Status(0,j,k);
}
}
return null;
case 1: //倒空B杯水
if(j>0) {
if(dp[i][0][k]>dp[i][j][k]+1) {
dp[i][0][k]=dp[i][j][k]+1;
path[i][0][k]=sta;
return new Status(i,0,k);
}
}
return null;
case 2: //倒空C杯水
if(k>0) {
if(dp[i][j][0]>dp[i][j][k]+1) {
dp[i][j][0]=dp[i][j][k]+1;
path[i][j][0]=sta;
return new Status(i,j,0);
}
}
return null;
case 3: //倒满A杯水
if(i<A) {
if(dp[A][j][k]>dp[i][j][k]+1) {
dp[A][j][k]=dp[i][j][k]+1;
path[A][j][k]=sta;
return new Status(A,j,k);
}
}
return null;
case 4: //倒满B杯水
if(j<B) {
if(dp[i][B][k]>dp[i][j][k]+1) {
dp[i][B][k]=dp[i][j][k]+1;
path[i][B][k]=sta;
return new Status(i,B,k);
}
}
return null;
case 5: //倒满C杯水
if(k<C) {
if(dp[i][j][C]>dp[i][j][k]+1) {
dp[i][j][C]=dp[i][j][k]+1;
path[i][j][C]=sta;
return new Status(i,j,C);
}
}
return null;
case 6: //B->A
if(j>0&&i<A) {
if(i+j<=A) {
if(dp[i+j][0][k]>dp[i][j][k]+1) {
dp[i+j][0][k]=dp[i][j][k]+1;
path[i+j][0][k]=sta;
return new Status(i+j,0,k);
}
}else {
if(dp[A][i+j-A][k]>dp[i][j][k]+1) {
dp[A][i+j-A][k]=dp[i][j][k]+1;
path[A][i+j-A][k]=sta;
return new Status(A,i+j-A,k);
}
}
}
return null;
case 7: //C->A
if(k>0&&i<A) {
if(i+k<=A) {
if(dp[i+k][j][0]>dp[i][j][k]+1) {
dp[i+k][j][0]=dp[i][j][k]+1;
path[i+k][j][0]=sta;
return new Status(i+k,j,0);
}
}else {
if(dp[A][j][i+k-A]>dp[i][j][k]+1) {
dp[A][j][i+k-A]=dp[i][j][k]+1;
path[A][j][i+k-A]=sta;
return new Status(A,j,i+k-A);
}
}
}
return null;
case 8: //A->B
if(i>0&&j<B) {
if(i+j<=B) {
if(dp[0][i+j][k]>dp[i][j][k]+1) {
dp[0][i+j][k]=dp[i][j][k]+1;
path[0][i+j][k]=sta;
return new Status(0,i+j,k);
}
}else {
if(dp[i+j-B][B][k]>dp[i][j][k]+1) {
dp[i+j-B][B][k]=dp[i][j][k]+1;
path[i+j-B][B][k]=sta;
return new Status(i+j-B,B,k);
}
}
}
return null;
case 9: //C-B
if(k>0&&j<B) {
if(j+k<=B) {
if(dp[i][j+k][0]>dp[i][j][k]+1) {
dp[i][j+k][0]=dp[i][j][k]+1;
path[i][j+k][0]=sta;
return new Status(i,j+k,0);
}
}else {
if(dp[i][B][j+k-B]>dp[i][j][k]+1) {
dp[i][B][j+k-B]=dp[i][j][k]+1;
path[i][B][j+k-B]=sta;
return new Status(i,B,j+k-B);
}
}
}
return null;
case 10: //A->C
if(i>0&&k<C) {
if(i+k<=C) {
if(dp[0][j][i+k]>dp[i][j][k]+1) {
dp[0][j][i+k]=dp[i][j][k]+1;
path[0][j][i+k]=sta;
return new Status(0,j,i+k);
}
}else {
if(dp[i+k-C][j][C]>dp[i][j][k]+1) {
dp[i+k-C][j][C]=dp[i][j][k]+1;
path[i+k-C][j][C]=sta;
return new Status(i+k-C,j,C);
}
}
}
return null;
case 11: //B->C
if(j>0&&k<C) {
if(j+k<=C) {
if(dp[i][0][j+k]>dp[i][j][k]+1) {
dp[i][0][j+k]=dp[i][j][k]+1;
path[i][0][j+k]=sta;
return new Status(i,0,j+k);
}
}else {
if(dp[i][j+k-C][C]>dp[i][j][k]+1) {
dp[i][j+k-C][C]=dp[i][j][k]+1;
path[i][j+k-C][C]=sta;
return new Status(i,j+k-C,C);
}
}
}
return null;
}
return null;
}