这道题使用dfs会超时,看评论区也有人遇到同样的问题,比赛时调试了1个多小时尝试改进,没有意识到应该换用非递归的bfs可以解决,消耗了大量的时间。
超时的方案如下,使用python实现:(经过尝试,能通过的测试用例中,使用5个方向就可以了)
1 import sys 2 class Solution: 3 def __init__(self): 4 self.visited = [] 5 self.distance = sys.maxsize 6 #self.direction = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]] 7 self.direction = [[1,1],[0,1],[1,0],[-1,1],[1,-1]] 8 #self.direction = [[1,1],[0,1],[1,0],[1,-1]] 9 #self.direction = [[1,1],[0,1],[1,0]] 10 11 def dfs(self,grid,N,i,j,distance): 12 if i == N-1 and j == N-1: 13 self.distance = min(self.distance,distance+1) 14 return 15 16 if distance >= self.distance: 17 return 18 19 if self.visited[i][j] == 0: 20 self.visited[i][j] = 1 21 distance += 1 22 for direct in self.direction: 23 x = i + direct[0] 24 y = j + direct[1] 25 if x < 0 or x >= N or y < 0 or y >= N: 26 continue 27 if grid[x][y] == 1 or self.visited[x][y] == 1: 28 continue 29 self.dfs(grid,N,x,y,distance) 30 distance -= 1 31 self.visited[i][j] = 0 32 33 34 def shortestPathBinaryMatrix(self, grid: 'List[List[int]]') -> int: 35 N = len(grid) 36 if grid[0][0] == 1 or grid[N-1][N-1] == 1: 37 return -1 38 self.visited = [[0 for _ in range(N)]for _ in range(N)] 39 40 self.dfs(grid,N,0,0,0) 41 return self.distance if self.distance < sys.maxsize else -1
暂时先这样吧。