自动搬运

查看原文

来自洛谷，原作者为

	NaVi_Awson 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:45:43，当前版本为作者最后更新于2016-11-26 15:19:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以不用dp，dfs和bfs也是可以的；

首先 dfs：f[i][j]表示两桶量分别为i，j是否出现过，就可以剪枝；

附上dfs代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
 using namespace std;
int x,y,k,m;
bool f[105][105];
int ans=1e9;
void dfs(int xn,int yn,int kn)
{
    if ((f[xn][yn]==1)||(kn-1>k)) return;
    f[xn][yn]=1;
    ans=min(ans,abs(m-xn-yn));
    dfs(x,yn,kn+1);
    dfs(xn,y,kn+1);
    dfs(0,yn,kn+1);
    dfs(xn,0,kn+1);
    if(x-xn<=yn) dfs(x,yn-(x-xn),kn+1);
    else dfs(xn+yn,0,kn+1);
    if(y-yn<=xn) dfs(xn-(y-yn),y,kn+1);
    else dfs(0,xn+yn,kn+1);
    f[xn][yn]=0;
    return;
}
int main() 
{   
    scanf("%d%d%d%d",&x,&y,&k,&m);
    dfs(0,0,1);
    cout<<ans<<endl;
    return 0;
}

其次bfs：思路差不多；c[i][j]表示得到第一个杯子i升，第二个杯子j升，最小的操作次数，也就是在搜索树中层数 初始(0,0)入队，两个杯子中的容量都是0

取出队列首元素：(p,q)

考虑子结点，任意一个杯子倒空，任意一个杯子装满，从一个杯子倒入另一个杯子

bfs代码就不贴了（其实我懒）