Python|利用BFS模板解决水壶问题

import math

def canMeasureWater(x,y,z):

    #首先处理几种极端情况

    if x+y<z:

        return False

    elif z==x or z==y:

        return True

    elif x==0 or y==0:

        return False

    #判断z是否能整除最大公约数

    return z%math.gcd(x,y)==0    #math.gcd()这个函数就是直接求出参数的最大公约数

#也可以用辗转相除法自己求最大公约数

def mygcd(x,y):

    while y:

        x,y=y,x%y

    return x

def BFS(graph,start,end):

    queue=[]#建立queue

queue.append([start])

Visited=set()#建立visited

    visited.add(start)

    while queue:#循环queue

        node=queue.pop()#处理节点

        visited.add(node)#更新visited

        process(node)

        nodes=generate_related_nodes(node)#扩展节点

        queue.push(nodes)#入queue

import collections

class Solution:

    def canMeasureWater(self, x: int, y: int, z: int) -> bool:

        # 首先处理几种极端情况

        if z<0 or x+y<z:return False

        # BFS

        queue=collections.deque([(0,0)])#建立queue，collections.deque是双端队列，支持从两端添加和删除元素

        visited={(0,0)}         #建立visited

        while len(queue):

            # current node processing处理当前节点

            a,b=queue.popleft()

            if a==z or b==z or a+b==z:

                return True

            #generate other nodes扩展更多节点

            states=self._gen_states(a,b,x,y)

            # check visited push node 更新visited 提交节点

            for state in states:

                if state not in visited:

                    visited.add(state)

                    queue.append(state)

        return False

    def _gen_states(self,a,b,x,y):

        states=[]

        #清空

        states.append((0,b))

        states.append((a,0))

        #填满水

        states.append((x, b))

        states.append((a, y))

        #a倒入b，a+b

        if a+b<y:

            states.append((0,a+b))

        else :

            states.append((a+b-y,y))

        #b倒入a，a+b

        if a+b<x:

            states.append((a+b,0))

        else:

            states.append((x,a+b-x))

        return states

# sol=Solution()

# print(sol.canMeasureWater(3,5,4))