Python: Depth-First Search(4)

Abstract: Search the shortest way on the map.




The results:
the shortest steps from A to B is 7 ( [[0, 1], [1, 1], [1, 2], [1, 3], [2, 3], [3, 3], [3, 2]] )
the shortest steps from A to B is none.


The script:

# -*- coding: utf-8 -*-
"""
Created on Sun Jun  7 18:44:43 2015

@author: yuan
"""
#the shortest way from (x,y) to (m,n) on a map


#depth first search
class depth_first:
   
    def __init__(self, map, start, end):
        self.pool=map
        self.steps=map
        self.start=start
        self.end=end
        self.out=[]# store all steps from (x,y) to (m,n)
        self.next=[[0,1], [1,0], [0,-1],[-1,0]]
     
    def DFS(self, point, steps, ways):
       
        #judge if reach the end point
        if (point[0]==self.end[0] and point[1]==self.end[1]):
            if (len(self.out) > len(steps)) or len(self.out)==0:
                self.out=list(steps)
            return
       
        #print 'step:', step
        for i in range(4):
            tx=point[0]+self.next[i][0]
            ty=point[1]+self.next[i][1]           
            #print tx,ty
            if (0<=tx<=4 and 1<=ty<=3):
                if(self.pool[tx][ty]==0 and ways[tx][ty]==0 ):
                    ways[tx][ty]=1
                    new_start=[tx,ty]
                    print new_start
                    steps.append(new_start)
                    self.DFS(new_start, steps, ways)
                    ways[tx][ty]=0
        return
           
    def shortest_way(self):
        ways=list(self.pool)
        steps=[]
        #search
        self.DFS(self.start, steps, ways)
        step_num=len(self.out)
        if step_num>0:
            print 'the shortest steps is ', step_num, '(', self.out, ')'
        else:
            print 'There is no ways'.
        return self.out

#main programming
#read the map
map=[[0,0,1,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,1,0,0,1],[1,0,0,1,0],[0,1,0,0,0]]

#coordinate of the start point
start=[0,0]

#coordinate of the end point
end=[3,2]
s=depth_first(map, start, end)
out=s.shortest_way()

#coordinate of the end point
end=[5,0]
s=depth_first(map, start, end)
out=s.shortest_way()