Water Jug problem bfs

#method 1:
from math import gcd
class Solution:
    def canMeasureWater(self, a: int, b: int, d: int) -> bool:
        if d>a+b:return False
        return d%gcd(a,b)==0

#to find no of steps
from math import gcd
def minSteps( m, n, d):
    return mins(m,n,d)
def find(m,n,d):
    x,y,c1=m,0,1
    while not(x==d or y==d ):
        val=min(x,n-y)
        x,y=x-val,y+val
        c1+=1
        if x==d or y==d:break
        if x==0:
            x=m
            c1+=1
        if y==n:
            y=0
            c1+=1
    return c1

def mins(m,n,d):
    if m<d and d>n:return -1
    if d%gcd(m,n)!=0:return -1
    c1,c2=0,0
    x,y=m,0
    a=find(m,n,d)
    b=find(n,m,d)
    return  min(a,b)
return minSteps(m,n,d)

#method 2:
from collections import deque
class Solution:
    def canMeasureWater(self, a: int, b: int, tar: int) -> bool:
        q=deque()
        q.append((0,0))
        vis=set()
        vis.add(0)
        while  q:
            for _ in range(len(q)):
                #print(q)
                t,c=q.popleft()
                for i in (a,b,-a,-b):
                    nt=t+i
                    if nt==tar:return True
                    if nt in vis:continue
                    vis.add(nt)
                    if 0<=nt<=a+b:q.append((nt,c+1))
        return False
 #method 3
from collections import deque
class Solution:
    def canMeasureWater(self, a: int, b: int, tar: int) -> bool:
        q=deque()
        q.append((0,0,0))
        vis=set()
        while q:
            for _ in range(len(q)):
                #print(q)
                i,j,c=q.popleft()
                if (i,j) in vis:continue
                vis.add((i,j))
                if not(0<=i<=a and 0<=j<=b):continue

                if i==tar or j==tar or i+j==tar:return True


                #pour water from jug2 to jug1

                q.append((min(i+j,a),max(j-(a-i),0),c+1))


                #pour water from jug1 to jug2
                q.append((max(i-(b-j),0),min(i+j,b),c+1))

                #empty jug1
                q.append((0,j,c+1))

                #empty jug2
                q.append((i,0,c+1))

                q.append((i,b,c+1))

                q.append((a,j,c+1))
        return False
  #method3: