网格图中最少访问的格子数
难度:
标签:
题目描述
You are given a 0-indexed m x n integer matrix grid. Your initial position is at the top-left cell (0, 0).
Starting from the cell (i, j), you can move to one of the following cells:
- Cells
(i, k)withj < k <= grid[i][j] + j(rightward movement), or - Cells
(k, j)withi < k <= grid[i][j] + i(downward movement).
Return the minimum number of cells you need to visit to reach the bottom-right cell (m - 1, n - 1). If there is no valid path, return -1.
Example 1:
Input: grid = [[3,4,2,1],[4,2,3,1],[2,1,0,0],[2,4,0,0]] Output: 4 Explanation: The image above shows one of the paths that visits exactly 4 cells.
Example 2:
Input: grid = [[3,4,2,1],[4,2,1,1],[2,1,1,0],[3,4,1,0]] Output: 3 Explanation: The image above shows one of the paths that visits exactly 3 cells.
Example 3:
Input: grid = [[2,1,0],[1,0,0]] Output: -1 Explanation: It can be proven that no path exists.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 1050 <= grid[i][j] < m * ngrid[m - 1][n - 1] == 0
代码结果
运行时间: 662 ms, 内存: 47.4 MB
/*
* 思路：
* 使用广度优先搜索（BFS）算法，从左上角开始遍历每一个格子，记录到达每个格子所需的最少步数。
* 使用Java Stream API来处理队列操作。
*/
import java.util.*;
import java.util.stream.Collectors;
public class SolutionStream {
public int minMoves(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] directions = {{0, 1}, {1, 0}};
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
visited[0][0] = true;
int moves = 0;
while (!queue.isEmpty()) {
List<int[]> currentLevel = queue.stream().collect(Collectors.toList());
queue.clear();
for (int[] current : currentLevel) {
int x = current[0];
int y = current[1];
if (x == m - 1 && y == n - 1) return moves;
for (int[] direction : directions) {
for (int step = 1; step <= grid[x][y]; step++) {
int nx = x + direction[0] * step;
int ny = y + direction[1] * step;
if (nx >= m || ny >= n) break;
if (!visited[nx][ny]) {
queue.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
moves++;
}
return -1;
}
}解释
方法:
这个题解采用的是动态规划的思想，结合一种特殊的数据结构来优化搜索过程。从网格的右下角开始反向思考到达左上角的最小步数，使用两个列表来维护可能的移动路径和步数。对于每一个格子，计算向左和向上移动的最小步数，如果这个步数小于当前记录的步数，则更新。这种方法通过从右下到左上的方式，逐步缩减搜索空间，并在过程中不断更新每个格子到达终点的最小步数。
时间复杂度:
O(m*n*log(n))
空间复杂度:
O(m*n)
代码细节讲解
🦆
题解中提到从右下角开始反向思考到达左上角的最小步数，这种反向思考的方法相比从左上角到右下角有什么优势？
▷🦆
在题解中使用的两个列表来维护可能的移动路径和步数，请问这些列表具体是如何更新和维护的？
▷🦆
题解中提到了使用动态规划的思想，能否详细解释这里的动态规划状态是如何定义的？
▷