TARGET DECK: Leetcode FILE TAGS: Medium
Intuition
Complexity
Runtime
Space
Code
Incorrect Code
The following code is incorrect, since dp would save the minimum possible distance from a given starting point, but that distance could be larger than the distance starting from a different point:
class Solution:
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
m, n = len(maze), len(maze[0])
def move(x, y, dx, dy):
dist = 0
while 0 <= x + dx < m and 0 <= y + dy < n and maze[x + dx][y + dy] == 0:
dist += 1
x += dx
y += dy
return x, y, dist
dp = {}
visited = set()
def dfs(r, c):
if [r, c] == destination:
return 0
if (r, c) in visited:
return inf
if (r, c) in dp:
return dp[(r, c)]
min_dist = inf
visited.add((r, c))
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_r, new_c, dist = move(r, c, dx, dy)
min_dist = min(min_dist, dist + dfs(new_r, new_c))
visited.remove((r, c))
dp[(r, c)] = min_dist
return min_dist
res = dfs(start[0], start[1])
if res == inf:
return -1
return resTodo
Find an concrete example as to why it does not work