BFS
被Python dict与list这种可变对象给坑了,这东西不需要声明全局变量就可以改变值呜呜呜
没什么好说的BFS的板子题,用个列表存储路径就可以了。
from collections import deque,defaultdict;
a,b,c = map(int,input().split());
g = {1:a,2:b};
def op(i,x,y):
if i == 0:
return full(1,x,y);
elif i == 1:
return full(2,x,y);
elif i == 2:
return drop(1,x,y);
elif i == 3:
return drop(2,x,y);
elif i == 4:
return pour(1,2,x,y);
elif i ==5:
return pour(2,1,x,y);
def full(i,x,y):
if i == 1:
return (g[1],y);
else:
return (x,g[2]);
def drop(i,x,y):
if i == 1:
return (0,y);
else:
return (x,0);
def pour(i,j,x,y):
# 需要k
f = {1:x,2:y}
k = g[j] - f[j];
# 有m
m = f[i];
# 能给z
z = min(k,m);
f[i] = m - z;
f[j] += z;
return f[1],f[2];
def bfs():
st = defaultdict(int);
# 做好映射,为最后输出方案做好准备
OP = {0:'FILL(1)',1:'FILL(2)',2:'DROP(1)',3:'DROP(2)',4:'POUR(1,2)',5:'POUR(2,1)'};
# 存储方案
res = defaultdict(list);
# 用int这种不可变对象存储当前A,B的水量
A,B = 0,0
q = deque([(A,B)])
st[(0,0)] = 1;
ans = 0;
while q:
for _ in range(len(q)):
x,y = q.popleft();
if x == c or y == c:
print(ans);
for i in res[(x,y)]:
print(i)
return True;
# 枚举所有可能的方案
for i in range(6):
new_x,new_y = op(i,x,y);
# 如果该方案出现过就必不可能是最短的方案
if (new_x,new_y) in st:continue;
q.append((new_x,new_y));
# 继承到达x,y的方案,因为列表为可变对象,要浅复制下
res[(new_x,new_y)] = res[(x,y)].copy();
# 添加x,y --- > new_w,new_y的方案
res[(new_x,new_y)].append(OP[i]);
# 标记一下
st[(new_x,new_y)] = 1;
ans += 1;
return False;
if not bfs():
print('impossible');