基本算法3

周游：
from enum import Enum
class COLORS(Enum):
    white=1
    gray=2
    black=3
class NODE(object):
    def __init__(self,value):
        self._value=value
        self.connections={}
        self._parent=None
        self._color=COLORS.white

    def __str__(self):
        return str(self._value)

    def getWeight(self,item):
        return self.connections.get(item,0)
    def addNeibor(self,item,weight=1):
        self.connections[item]=weight

    @property
    def color(self):
         return self._color
    @color.setter
    def color(self,value):
        self._color=value

    @property
    def value(self):
        return self._value

    @value.setter
    def value(self,value):
        self._value=value
    @property
    def parent(self):
        return self._parent
    @parent.setter
    def parent(self,item):
        self._parent=item


    def getNeibor(self):
        return self.connections.keys()

    def getNeiborByOrder(self):
        ret=[]
        for neibor in self.getNeibor():
            if neibor.color==COLORS.white:
                sons=[son for son in neibor.getNeibor() if son.color==COLORS.white]
                ret.append((len(sons),neibor))
        ret.sort(key=lambda x:x[0])
        return [son[-1] for son in ret]


    def setParent(self,item):
        self.parent=item

    @property
    def dis(self):
        return self._dis

    @dis.setter
    def dis(self,value):
        self._dis=value



class GRAPH(object):
    def __init__(self):
        self.sons={}
        self.size=0

    def show(self):
        for item in self.getall():
            return  (item)

    def addSon(self,value):
        self.sons[value]=NODE(value)
        self.size +=1

    def getSon(self,value):
        return self.sons.get(value,None)
    def getall(self):
        return  self.sons.values()

    def addEdge(self,value1,value2,weight=1):
        if value1 not in self.sons:
            self.addSon(value1)
        if value2 not in self.sons:
            self.addSon(value2)
        self.sons[value1].addNeibor(self.sons[value2],weight)

def creatSons(m,n,row,col):
    steps=[(-2,-1),(-2,1),(-1,-2),(-1,2),
          (2,-1),(2,1),(1,-2),(1,2)]
    legal_pos=[]
    for step in steps:
        x=row+step[0]
        y=col+step[1]
        if x>0 and x<m+1:
            if y>0 and y<n+1:
                legal_pos.append((x,y))
    return legal_pos

def genId(m,n,row,col):
    return (row-1)*m+col

def genData(m,n):
    g=GRAPH()
    for i in range(1,m+1):
        for j in range(1,n+1):
            neibors=creatSons(m,n,i,j)
            for neibor in neibors:
                g.addEdge(genId(m,n,i,j),genId(m,n,neibor[0],neibor[1]))
    return g

def lvYou(total_steps,current,num,path):
    if num != total_steps:
        current.color=COLORS.gray
        flag=False
        for son in current.getNeiborByOrder():
            if son.color == COLORS.white :
                flag=lvYou(total_steps,son,num+1,path)
            if  flag:
                path.append(current)
                break
        if not flag:
            current.color=COLORS.white
        else:
            return True
    else:
        print(‘sucess‘,num,total_steps)
        current.color=COLORS.gray
        path.append(current)
        return True

def main():
    m=8
    n=8
    start=genId(m,n,1,1)
    g=genData(m,n)

    item=g.getSon(start)
    path=[]
    lvYou(m*n,item,1,path)
    print(‘====>>>>>‘,len(path))
    tt=[]
    for item in path:
        print(item)
    
main()