KK's blog

每天积累多一些

0%

LeetCode 1293 Shortest Path in a Grid with Obstacles Elimination

Posted on Disqus:

LeetCode



You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Example 1:



Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6
Explanation:
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).


Example 2:



Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1
Explanation: We need to eliminate at least two obstacles to find such a walk.


Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 40 1 <= k <= m * n
grid[i][j] is either 0 or 1. grid[0][0] == grid[m - 1][n - 1] == 0

题目大意：

矩阵从左上走到右下，但含障碍，现在可以移除k个，使得路径最短，求最短路径

解题思路：

求最短路径用BFS，但此题难点在于distance跟路径有关，比如某一格可能属于不同的路径，此时它的distance会不同，所以distance不能global，必须作为state传到下一个迭代
同样的情况也在visited中存在，visited跟路径相关，而这一格跟k相关，这一格可以被属于不同的k的路径访问，所以visited应该加入k

解题步骤：

N/A

注意事项：

  1. visited是(x, y, k), queue是(x, y, k, dis)
  2. (x, y, k - 1)跟visited比较，而不是(x, y, k)。下一个节点的条件为eleminatios >= 0
  3. 若k过多会LTE, 因为广度会过大。这是用曼哈顿距离来剪枝。左上到右下距离为m - n + 2这肯定是最短距离，若k大于等于这个数，也就是可以移除曼哈顿路径上的所有障碍。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shortestPath(self, grid: List[List[int]], k: int) -> int:
	m, n = len(grid), len(grid[0])
	if k >= m + n - 2: # TLE
		return m + n - 2

	queue = collections.deque([(0, 0, k, 0)]) # x, y, k, distance
	visited = set([(0, 0, k)]) # include k
	while queue:
		_x, _y, _k, _dis = queue.popleft()
		if _x == m - 1 and _y == n - 1:
			return _dis
		for _dx, _dy in OFFSET:
			x, y = _x + _dx, _y + _dy
			if x < 0 or x >= m or y < 0 or y >= n:
				continue
			eliminations = _k - 1 if grid[x][y] == 1 else _k
			if (x, y, eliminations) not in visited and eliminations >= 0:
				queue.append((x, y, eliminations, _dis + 1))
				visited.add((x, y, eliminations))
	return -1

算法分析：

时间复杂度为O(nmk)，空间复杂度O(mnk), 某个cell都可能被访问k次，因为最多有k条路径

Free mock interview