DFS经典题，reachable or not in a 2D maze

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

给定类似上面个一个 m by n matrix。其中0代表可以走的路，1代表不能走的墙。任意给出起点坐标(i, j)判段是否能从起点走到用2标出来的目标点？

 grid = [[0, 0, 0, 0, 0, 1],

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

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

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

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

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

 def dfsSearch(x, y):

     if grid[x][y] == 2:

         print('found at %d,%d' %(x, y))

         return True

     elif grid[x][y] == 1:

         print('Wall at %d,%d' %(x, y))

     elif grid[x][y] == 3:

         print('Visited before: %d, %d' %(x, y))

         return False

     print('Visiting %d,%d' %(x, y))

     # mark as visited

     grid[x][y] = 3

     # explore neighbors clockwise starting by the one on the right

     if ((x < len(grid) - 1) and dfsSearch(x + 1, y)) or \

             (y > 0 and dfsSearch(x, y - 1)) or \

             (x > 0 and dfsSearch(x - 1, y)) or \

             ((y < len(grid) - 1) and dfsSearch(x, y + 1)):

         return True

     return False

这个算法只是检查能不能找到符合要求的path，但是不保证找到的那一条path是最短的。注意把已经访问过的点设置成3，这样访问过的点就不会被重复访问了。

如果想要找出shortest path的长度，可以用如下的方法：

 class findShortestPath(object):

     def __init__(self):

         self.minLen = [0x7FFFFFFF]

     def shortPath(self, x, y):

         minLen = [999999]

         self.shortPathHelper(x, y, 0)

         return min(minLen)

     def shortPathHelper(self, x, y, step):

         nextStep = [[0, 1], [1, 0], [0, -1], [-1, 0]]

         if grid[x][y] == 2:

             print('found at %d,%d' % (x, y))

             self.minLen.append(step)

             return True

         elif grid[x][y] == 1:

             print('Wall at %d,%d' % (x, y))

         elif grid[x][y] == 3:

             print('Visited before: %d, %d' % (x, y))

             return False

         grid[x][y] = 3

         for k in range(4):

             tx = x + nextStep[k][0]

             ty = y + nextStep[k][1]

             if (tx < 0 or tx > len(grid)-1 or ty < 0 or ty > len(grid)-1):

                 continue

             self.shortPathHelper(tx, ty, step + 1)

巴特西

DFS经典题，reachable or not in a 2D maze

最新文章

热门文章