三个容器倒水问题---BFS

问题描述

有装满水的6升的杯子，空的3升杯子和1升杯子，3个杯子中都没有刻度。在不使用其他道具的情况下，是否可以量出4升的水呢？

注意：由于没有刻度，用杯子x给杯子y倒水时必须一直持续到把杯子y倒满或者把杯子x倒空，而不能中途停止。

你的任务是解决一般性的问题：设大、中、小3个杯子的容量分别为a,b,c，最初只有大杯子装满水，其他两个杯子为空。最少需要多少步才能让某一个杯子中的水有x升呢？你需要打印出每步操作后各个杯子中的水量（0<c<b<a<1000）。

思路

把每次操作的结果看成一个结点，画出图

使用BFS加上适当的剪枝就可以算出最少多少步可以得到目标结果

代码

#输入三个杯子的容量和目标量
m=list(map(int,input().split()))
a,b,c,d=m[0],m[1],m[2],m[3]
#杯子容量
nums=[]
nums.append(a)
nums.append(b)
nums.append(c)
#初始操作类型
kinds=[[]]
kinds[-1].append(nums[0])
kinds[-1].append(0)
kinds[-1].append(0)
n=0
#操作类型
kind=[[]]
kind[-1].append(nums[0])
kind[-1].append(0)
kind[-1].append(0)
if a<d:print("水的总量不及目标")
def con(kinds,n):global nums,d,kindend=[]for i in range(len(kinds)):for a in range(len(kinds[i])):for b in range(len(kinds[i])):if a==b:continueif kinds[i][b]==nums[b]:continuetemp_a=kinds[i][a]temp_b=kinds[i][b]if kinds[i][a]>=nums[b]-kinds[i][b]:kinds[i][a]-=(nums[b]-kinds[i][b])kinds[i][b]=nums[b]else:kinds[i][b]+=kinds[i][a]kinds[i][a]=0if kinds[i][a]==d or kinds[i][b]==d:end.append([])end[-1].append(kinds[i][0])end[-1].append(kinds[i][1])end[-1].append(kinds[i][2])print(end[-1],n)return iif kinds[i] not in kind:end.append([])end[-1].append(kinds[i][0])end[-1].append(kinds[i][1])end[-1].append(kinds[i][2])kind.append([])kind[-1].append(kinds[i][0])kind[-1].append(kinds[i][1])kind[-1].append(kinds[i][2])kinds[i][a]=temp_akinds[i][b]=temp_bcon(end,n+1)con(kinds,1)

不足之处欢迎在评论区提出