[[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)