简单迷宫问题

迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经过多次试验终于得到它学习走通迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从mg[1][1]出发，出口位于mg[n][m]

用一种标志在二维数组中标出该条通路，并在屏幕上输出二维数组。

  

   

    

     

    
    

     

      m=[[1,1,1,0,1,1,1,1,1,1],
     
    
   

    

     

    
    

     

         [1,0,0,0,0,0,0,0,1,1],
     
    
   

    

     

    
    

     

         [1,0,1,1,1,1,1,0,0,1],
     
    
   

    

     

    
    

     

         [1,0,1,0,0,0,0,1,0,1],
     
    
   

    

     

    
    

     

         [1,0,1,0,1,1,0,0,0,1],
     
    
   

    

     

    
    

     

         [1,0,0,1,1,0,1,0,1,1],
     
    
   

    

     

    
    

     

         [1,1,1,1,0,0,0,0,1,1],
     
    
   

    

     

    
    

     

         [1,0,0,0,0,1,1,1,0,0],
     
    
   

    

     

    
    

     

         [1,0,1,1,0,0,0,0,0,1],
     
    
   

    

     

    
    

     

         [1,1,1,1,1,1,1,1,1,1]]
     
    
   

    

     

    
    

     

      sta1=0;sta2=3;fsh1=7;fsh2=9;success=0
     
    
   

    

     

    
    

     

      def LabyrinthRat():
     
    
   

    

     

    
    

     

       print('显示迷宫：')
     
    
   

    

     

    
    

     
 for i in range(len(m)):print(m[i])
     
    
   

    

     

    
    

     

       print('入口：m[%d][%d]：出口：m[%d][%d]'%(sta1,sta2,fsh1,fsh2))
     
    
   

    

     

    
    

     
 if (visit(sta1,sta2))==0:	print('没有找到出口')
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       print('显示路径：')
     
    
   

    

     

    
    

     
 for i in range(10):print(m[i])
     
    
   

    

     

    
    

     

      def visit(i,j):
     
    
   

    

     

    
    

     

       m[i][j]=2
     
    
   

    

     

    
    

     
 global success
     
    
   

    

     

    
    

     
 if(i==fsh1)and(j==fsh2): success=1
     
    
   

    

     

    
    

     
 if(success!=1)and(m[i-1][j]==0): visit(i-1,j)
     
    
   

    

     

    
    

     
 if(success!=1)and(m[i+1][j]==0): visit(i+1,j)
     
    
   

    

     

    
    

     
 if(success!=1)and(m[i][j-1]==0): visit(i,j-1)
     
    
   

    

     

    
    

     
 if(success!=1)and(m[i][j+1]==0): visit(i,j+1)
     
    
   

    

     

    
    

     
 if success!=1: m[i][j]=3
     
    
   

    

     

    
    

     
 return success
     
    
   

    

     

    
    

     

      LabyrinthRat()
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/83064066