如何不重复的遍历矩形图（2）

客官°小女子只卖身不卖艺 2022-01-31 13:19 67阅读 0赞

先把代码贴上，回头再来补充

import  json
    import sys
    
    #coding=utf-8  
    # scope:0=<x<=6   1=<y<=11 
    index=[]
    re={}
    visited=[]
    ans=[]
    def read_source(): # 
      with open("rmonMap.json",'r') as load_f:
        load_dict = json.load(load_f)  
        data=load_dict
        for i,j in data.items():
           if i=="Map":
               data_v1=data[i]
               for h,k in data_v1.items():
                     if h=="Cells":
                          re=data_v1[h]
                         
                          return re
    
    def oriation(a):
            a_=0
            con_a=a_con=''
            a=list(a)
            for i in range(0,len(a)-1):
                if a[i]=='_':
                      a_=i
            for i in range(0,len(a)):
                if i<a_:
                     a_con=a_con+a[i]
                elif i>a_:
                   con_a=con_a+a[i]
            return int(a_con),int(con_a)
    
    def pan_duan(x,y):
        
        #if  0<=x<=12   and   12<=y<=14  :#abs the asseram
        if  0<=x<=6   and   1<=y<=11  :#abs the asseram
             #print("success")
             return True
        else:
             return False
    
    def divide_graph(re,g_x1,g_y1,g_x2,g_y2,g_x3,g_y3,g_x4,g_y4):# one to two
        graph1=[]
        graph2=[]
        for i in range(0,len(re)): 
                     for a,b in re[i].items(): 
                          if a=="Key": 
                                a_con,con_a=oriation(b)      
                                result=pan_duan(a_con,con_a) 
                                if result==True:
                                     graph1.append(re[i])
                                else:
                                     graph2.append(re[i]) 
        return graph1,graph2                              
    
    def create_graph(source):
        #print(source)
        route={}
        ture=1  
        for i in range(0,len(source)):#len(source)=2
            #print(source[i],len(source))
            a=source[i]
            #print(a)
            index=0
            for i,j in a.items():
                if i=="X":
                    index_x=j
                if i=="Y":
                    index_y=j
                if i=="E" or i=="W" or i=="N" or i=="S":
                    index=index+1
            arr_2=2
            arr_3=3
            for i,j in a.items():      
                    if i=="Key":
                        order=j   
                        if index==0:
                            route[j]={}
                        elif index==1:
                            route[j]={"E"}
                        elif index==2:
                            route[j]={"E","S"}
                        elif index==3:
                            route[j]={"E","S","W"}
                        elif index==4:
                            route[j]={"E","S","W","N"}
                        else:  
                            route[j]={}
                             
            for p ,j in a.items():
                if j==str(order):
                    #print("success")
                    #print(route[j])
                    arr=list(route[j])
                    #print(arr)
    
            for i,j in a.items():
                arr_2=arr_2-1
                if i=="E":
                        #print("i:",i)
                        E_X=index_x+1  
                        c=str(E_X)+"_"+str(index_y)
                       # print("C",c)
                        if index==4:
                            arr[0]=c
                        if index==1:
                            arr[0]=c
                        if index==2:
                            arr[arr_2]=c
                            
                        if index==3:
                           arr_3=arr_3-1
                           arr[arr_3]=c
                if i=="S":
                       # print("i:",i)
                        E_Y=index_y+1
                       # print(E_Y)
                        c=str(index_x)+"_"+str(E_Y)
                        #print("C",c)  
                        if index==4:
                            arr[1]=c
                        if index==1:
                            arr[0]=c
                        if index==2:
                            arr[arr_2]=c
                        if index==3:
                           arr_3=arr_3-1
                           arr[arr_3]=c
                if i=="W":  
                       # print("i:",i)
                        E_X=index_x-1
                        c=str(E_X)+"_"+str(index_y)
                        if index==4:
                            arr[2]=c
                        if index==1:
                            arr[0]=c
                        if index==2:
                            arr[arr_2]=c
                        if index==3:
                             arr_3=arr_3-1
                             arr[arr_3]=c
                if i=="N":   
                       # print("i:",i)
                        E_Y=index_y-1
                        c=str(index_x)+"_"+str(E_Y)
                        if index==4:
                            arr[3]=c
                        if index==1:
                            arr[0]=c
                        if index==2:
                            arr[arr_2]=c
                            
                        if index==3:
                            arr_3=arr_3-1
                            arr[arr_3]=c
            for i , j in route.items():
              #  print(i,j)
                if i==str(order): 
                   # print("success")
                    route[order]=arr
        #print("****************************")
        return route# zhi yu xia dui ying ke yi dao da de dian
    
    def com(a,b):
        flag=[]
        for i in range(0,len(b)):
            flag.append(0)
            for j in range(0,len(a)):
                if b[i]==a[j]:
                    flag[i]=1
                    break 
        for i in range(0,len(b)):
            if flag[i]==0:
                print("***********error************")
                b.remove(b[i])
        return b
    
    def check_graph(graph):
        a=[]
        b=[]
        c=[]
        for i,j in graph.items():
             a.append(i)
        for i,j in graph.items():
                b.append(j)
                for n in b:
                    data=n
                for y in data: 
                    c.append(y)
                c=com(a,c)
                graph[i]=c
                b=[]
                c=[]
        return graph
    
    def add_graph(graph):# create the key of graph
        index=[]
        for i in range(0,len(graph)):
            d=graph[i]
            
            for g,h in d.items():
                if g=='E' or g=='S' or g=='W' or g=='N':
                       flag=1     
            for g,h in d.items():
                 if g=='Key' and flag==1:
                      index.append(h)               
                      flag=0          
        return index      
    
    def create_oriation(a,b):
            a,b=str(a),str(b)
            
            a_=b_=0
            con_a=con_b=a_con=b_con=''
            a,b=list(a),list(b)
            for i in range(0,len(a)-1):
                if a[i]=='_':
                      a_=i
            for i in range(0,len(b)-1):
                if b[i]=='_':
                      b_=i
            for i in range(0,len(a)):
                if i<a_:
                     a_con=a_con+a[i]
                elif i>a_:
                   con_a=con_a+a[i]
    
            for i in range(0,len(b)):
                  if i<b_:
                     b_con=b_con+b[i]
                  elif i>b_:
                   con_b=con_b+b[i]
            #print("a_con",a_con,"con_a:",con_a,"b_con:",b_con,"con_b:",con_b)
    
            if a_con == b_con and  abs(int(con_a)-int(con_b))==1:
                      #print("success!")
                      return True
            elif con_a==con_b  and abs(int(a_con)-int(b_con))==1:
                       #print("success!")
                       return True
            else:
                       #print("error!")
                       return False 
    
    def list_to_dict(index):
         test={}
         for i in range(0,len(index)):
             value=[]
             for j in range(0,len(index)):
                   if i!=j:
                       result=create_oriation(index[i],index[j])
                       if  result==True:
                            val=str(index[j])
                            value.append(val)
             test[str(index[i])]=value
         return test
    
    
    
    def quick_sort(mylist,start,end):
        if start<end:
            i,j=start,end
            base = mylist[i]
            while i<j:
                    while(i<j) and (mylist[j]>=base):
                         j=j-1
                    mylist[i]=mylist[j]
                    while(i<j) and (mylist[i]<=base):
                          i=i+1
                    mylist[j]=mylist[i]
            mylist[i]=base
            quick_sort(mylist,start,i-1)
            quick_sort(mylist,i+1,end)
        return mylist 
    
    def sort_vector(key):
      
        te=[]
        ans=[]
        test={}
        for i in range(0,len(key)):
            add=0
            i_con,con_i=oriation(key[i])
            add=int(i_con)+int(con_i)
         
            te.append(add)
            test[key[i]]=add
        quick_sort(te,0,len(te)-1)
    
    
        for i in range(0,len(te)):
            for h,j in test.items():
                   
                    if te[i]==j:
                        ans.append(h)
                        break
        return ans 
    def select_start(G):
        #print("index:",index )
        te=[]
        test={}
        #print("index:",index)
        for i in range(0,len(index)-1):
             add=0
             a_con,con_a =oriation(index[i])
             #print(a_con,con_a)
             add=a_con+con_a
             test[index[i]]=add
             te.append(add)
        
        te=quick_sort(te,0,len(te)-1)
        
        for i in G.keys():
              re=0
              a_con,con_a=oriation(i)
              re = a_con+con_a
              if re==te[0]:
                  # print("min:",i)
                   min=i
              elif re==te[len(test)-1]:
                   #print("max:",i)
                   max=i
        return min,max
    def add_way(key,start,flag,sig):# key from  min to max
        way=[]
        s_con,con_s=oriation(start)
        k0_con,con_k0=oriation(key[0])
        km_con,con_Km=oriation(key[len(key)-1])
        print(s_con,con_s,k0_con,con_k0,km_con,con_Km)
        if flag==1 and sig==1:
            print("11111")
            if  ( s_con<k0_con or con_s<con_k0 ):# start is  min 
               print("111 dada")
               for i in key:
                    if i not in visited:
                             way.append(i)
            elif ( s_con>km_con or con_s>con_Km ):# start is the max
              print("1111 xiaoxiao")
              for i in range(len(key)-1,-1,-1):
                    if i not in visited:
                             way.append(key[i])
        if  flag==0 and sig==1:#  x is the different ,y is the same 
             if  ( s_con<k0_con or con_s<con_k0 ):# start is  min 
               for i in key:
                    if i not in visited:
                             way.append(i)
                             break#  only one is add 
             elif ( s_con>km_con or s_con>km_con ):# start is the max
                for i in range(len(key)-1,-1,-1):
                    if i not in visited:
                             way.append(key[i])     
                             break  # only one is add
        if flag==0 and sig ==0:
            if  ( s_con<k0_con or con_s<con_k0 ):# start is  min 
               print("111 dada")
               for i in key:
                    if i not in visited:
                             way.append(i)
                             
            elif ( s_con>km_con or con_s>con_Km ):# start is the max
              print("1111 xiaoxiao")
              for i in range(len(key)-1,-1,-1):
                    if i not in visited:
                             way.append(key[i]) 
                             
        if flag==1 and sig ==0:
            if  ( s_con<k0_con or con_s<con_k0 ):# start is  min 
               print("111 dada")
               for i in key:
                    if i not in visited:
                             way.append(i)
                             break
            elif ( s_con>km_con or con_s>con_Km ):# start is the max
              print("1111 xiaoxiao")
              for i in range(len(key)-1,-1,-1):
                    if i not in visited:
                             way.append(key[i])
                             break
        print("way:",way)
        return way
    
    def select_vector( min,flag,max,sig):
      visited=[]
      visited.append(min)
      a_con,con_a=oriation(min)
      print("way6666:",visited,flag)
      while len(visited)<len(index):
                print( "len(visited)",len(visited),"len(index):",len(index))
                if flag==0:  
                    start = visited[len(visited)-1]
                    s_con,con_s=oriation(start)
                    key=[]
                    for i in index:
                            i_con,con_i=oriation(i)
                            if  i_con!=s_con and con_i==con_s:
                                if i not in visited:
                                    key.append(i)
                                        
                    
                    key=sort_vector(key)
                    
                    print(key,start,flag)
                    
                    re=add_way(key,start,flag,sig)
                    visited=visited+re
                    print("666666666visited:",visited,len(visited),flag)
                    
                    #break
                    flag=1    
                elif flag==1:
                    start = visited[len(visited)-1]
                    s_con,con_s=oriation(start)
                    key=[]
                    for i in index:
                            i_con,con_i=oriation(i)
                            if  i_con==s_con and con_i!=con_s:
                                if i not in visited:
                                    key.append(i) 
                    key=sort_vector(key)
                    
                    print("key:",key,"start:",start,"flag:",flag)
                    
                    re=add_way(key,start,flag,sig)
                    
                    visited=visited+re
                    print("visited:",visited,len(visited))
                   
                    
                    flag=0             
      
      return visited
    def quick_graph_bianli(G,min,max): #create four vector 
            i_x,i_y=oriation(min)
            a_x,a_y=oriation(max) 
            print(i_x,i_y,a_x,a_y)
            flag=symbol=0
            if abs(i_x-a_x)<abs(i_y-a_y):#the best way is y ,x is the same
                    flag=1  
                    symbol=1
            else:                        #the best way is x ,y is the same
                    flag=0
                    symbol=0 
                   
            return flag,symbol
    def main():
         re=read_source()
         graph1,graph2=divide_graph(re,0,12,6,12,0,14,5,14)
         G=create_graph(graph1)     
         for i in G.keys(): ### this is all graph 
               index.append(i)
         min,max=select_start(G)
         print(min,max)
         flag,symbol=quick_graph_bianli(G,min,max)
         print("flag:",flag,"symbol:",symbol)
         ans=select_vector(min,flag,max,symbol)
         print("ans:",ans)
    main()

最后的输出：('visited:', \[u'0\_1', u'0\_2', u'0\_3', u'0\_4', u'0\_5', u'0\_6', u'0\_7', u'0\_8', u'0\_9', u'0\_10', u'0\_11', u'1\_11', u'1\_10', u'1\_9', u'1\_8', u'1\_7', u'1\_6', u'1\_5', u'1\_4', u'1\_3', u'1\_2', u'1\_1', u'2\_1', u'2\_2', u'2\_3', u'2\_4', u'2\_5', u'2\_6', u'2\_7', u'2\_8', u'2\_9', u'2\_10', u'2\_11', u'3\_11', u'3\_10', u'3\_9', u'3\_8', u'3\_7', u'3\_6', u'3\_5', u'3\_4', u'3\_3', u'3\_2', u'3\_1', u'4\_1', u'4\_2', u'4\_3', u'4\_4', u'4\_5', u'4\_6', u'4\_7', u'4\_8', u'4\_9', u'4\_10', u'4\_11', u'5\_11', u'5\_10', u'5\_9', u'5\_8', u'5\_7', u'5\_6', u'5\_5', u'5\_4', u'5\_3', u'5\_2', u'5\_1', u'6\_1', u'6\_2', u'6\_3', u'6\_4', u'6\_5', u'6\_6', u'6\_7', u'6\_8', u'6\_9', u'6\_10', u'6\_11'\], 77)  
('ans:', \[u'0\_1', u'0\_2', u'0\_3', u'0\_4', u'0\_5', u'0\_6', u'0\_7', u'0\_8', u'0\_9', u'0\_10', u'0\_11', u'1\_11', u'1\_10', u'1\_9', u'1\_8', u'1\_7', u'1\_6', u'1\_5', u'1\_4', u'1\_3', u'1\_2', u'1\_1', u'2\_1', u'2\_2', u'2\_3', u'2\_4', u'2\_5', u'2\_6', u'2\_7', u'2\_8', u'2\_9', u'2\_10', u'2\_11', u'3\_11', u'3\_10', u'3\_9', u'3\_8', u'3\_7', u'3\_6', u'3\_5', u'3\_4', u'3\_3', u'3\_2', u'3\_1', u'4\_1', u'4\_2', u'4\_3', u'4\_4', u'4\_5', u'4\_6', u'4\_7', u'4\_8', u'4\_9', u'4\_10', u'4\_11', u'5\_11', u'5\_10', u'5\_9', u'5\_8', u'5\_7', u'5\_6', u'5\_5', u'5\_4', u'5\_3', u'5\_2', u'5\_1', u'6\_1', u'6\_2', u'6\_3', u'6\_4', u'6\_5', u'6\_6', u'6\_7', u'6\_8', u'6\_9', u'6\_10', u'6\_11'\])