第一次作深度优先算法的题,下次作广度优先算法python
P.S.web
代码(参考了网站上的题解):算法
class Solution: def hasValidPath(self, grid) -> bool: # 2 #3 1 # 4 # road[street_num][in]=road_out #代码造成过程当中的递归深度会很深,因此须要用sys.setrecursionlimit来扩充递归调用深度 import sys sys.setrecursionlimit(1000000) road=[[-1 for i in range(4)] for _ in range(6)] road[0][2]=2 road[0][0]=0 road[1][1]=1 road[1][3]=3 road[2][0]=3 road[2][1]=2 road[3][1]=0 road[3][2]=3 road[4][0]=1 road[4][3]=2 road[5][2]=1 road[5][3]=0 way_x=[0, -1, 0, 1] way_y=[1, 0, -1, 0] leng_x=len(grid) leng_y=len(grid[0]) def dsf(x, y, road_in, grid) -> bool: if (x==leng_x-1 and y==leng_y-1): if road[grid[x][y]-1][road_in]>=0: return True elif (x<0 or y<0 or x>=leng_x or y>=leng_y): return False street_num=grid[x][y]-1 road_out=road[street_num][road_in] x=x+way_x[road_out] y=y+way_y[road_out] if road_out == -1: return False else: return dsf(x, y, road_out, grid) for road_in in [0, 1, 2, 3]: if road[grid[0][0]-1][road_in]>=0: if dsf(0,0,road_in,grid): return True return False