用bfs实现倒水问题

zengli17

你有两个容积分别为a,b杯子  你每次可以将某个杯子中的水倒满或者倒掉或者倒到另一个杯子  问能否通过这两个杯子量出c容量的水

和上一个倒可乐问题类似  只是这个操作更多了点  将两个杯子中各含有的水作为状态  每出队列一个状态  将所有可能到达的状态入队  直到有一个杯子里面水的体积为c   打印路径直接递归就行了

zengli17

给出了两个瓶子的容量A,B, 以及一个目标水量C，

对A、B可以有如下操作:

FILL(i)        fill the pot i (1 ≤ i ≤ 2) from the tap;

DROP(i)      empty the pot i to the drain;

POUR(i,j)    pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).

问经过哪几个操作后能使得任意一个瓶子的残余水量为C。

若不可能得到则输出impossible

zengli17

class State:
    def __init__(self,a,b,prev,step,operation):
        self.a=a
        self.b=b
        self.prev=prev
        self.step=step
        self.operation=operation
visited = [ [ False for j in range( 100 ) ] for i in range( 100 ) ]


def bfs(capacity_a,capacity_b,left_c):
    queue=[]
    visited[0][0]=True
    s=State( a=0,b=0,prev=None,step=0, operation=None)
    queue.append(s)
    while queue:
        state=queue.pop(0)
        for i in range(6):
            a,b,operation=None,None,None
            if i==0:
                operation='往a杯子里到满水'
                a=capacity_a
                b=state.b
            elif i==1:
                operation='往b杯子里到满水'
                a=state.a
                b=capacity_b
               
            elif i==2:
                operation='把a杯子里的水放空'
                a=0
                b=state.b
            elif i==3:
                operation='把b杯子里的水放空'
                a=state.a
                b=0
            elif i==4:
                if state.a + state.b > capacity_a:
                    operation="向a杯水中倒入b杯水直到a杯水满"
                    a=capacity_a
                    b=state.a + state.b - capacity_a
                else:
                    operation='向a杯水中倒入b杯水直到b杯空'
                    a=state.a + state.b
                    b=0
            elif i==5:
                if state.a + state.b > capacity_b:
                    operation="向b杯水中倒入a杯水直到b杯水满"
                    a=state.a + state.b - capacity_b
                    b=capacity_b
                else:
                    operation='向b杯水中倒入a杯水直到a杯空'
                    a=0
                    b=state.a + state.b
                    
            if not visited[a][b]:
                new_state = State( a = a, b = b, prev = state, step = state.step + 1,operation=operation)
                queue.append(new_state)
                visited[a][b]=True
                if a==left_c or b==left_c:
                    return new_state
    return None

def get_path(state):
    path=[]
    while state.prev:
        path.append(state.operation)
        state=state.prev
    return path[::-1]

def main():
    capacity_a = int( input( "输入 a 杯子容量: " ) )
    capacity_b = int( input( "输入 b 杯子容量: " ) )
    left_c = int( input( "输入需要获得的水量: " ) )

    answer=bfs(capacity_a,capacity_b,left_c)
    if answer:

        path=get_path(answer)
        print(path)
    else:
        print('此题无解')


main()

jerryxjr1220

http://bbs.fishc.com/thread-82154-1-2.html