Minimum Number of Visited Cells in a Grid
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) with j < k <= grid[i][j] + j (rightward movement), or
- Cells (k, j) with i < 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 \ \mathrm{==} \ \text{grid.length}$
- $n \ \mathrm{==} \ \text{grid}[i]\text{.length}$
- $1 \leq m, n \leq {10}^5$
- $1 \leq m \times n \leq {10}^5$
- $0 \leq \text{grid}[i][j] < m \times n$
- $\text{grid}[m - 1][n - 1] \ \mathrm{==} \ 0$
解题思路
与方格迷宫很像，每个节点能够到达的节点数很多，因此在bfs时需要枚举的边数很多。但这题只有向右和向下两个方向，其他的条件与方格迷宫也很像，因此可以用相同的剪枝策略。
即从$(x,y)$枚举能到达的格子$(x',y')$，如果有$d_{x',y'} < d_{x, y} + 1$，那么就$\text{break}$，因为用$(x',y')$更新后面的格子得到的结果不比$(x,y)$差。这样可以保证在同一个方向上所有格子最多会被枚举到$2$次，两个方向一共最多会枚举$4 \times nm$次，因此时间复杂度就是$O(nm)$，证明的话可以参考方格迷宫。
这题在剪枝的时候还要个地方需要注意，因为每个格子能扩展的距离不一定相同，比如从$(x',y')$向右最大能扩展到$(x',y'+g[x'][y'])$，$(x,y)$向右最大能扩展到$(x,y+g[x][y])$，而$y'+g[x'][y'] < y+g[x][y]$，现在有$d_{x',y'} < d_{x, y} + 1$，如果此时直接$\text{break}$，那么$\left[ y'+g[x'][y'] + 1 \sim y+g[x][y] \right]$中还没有枚举到的格子就无法被$(x,y)$更新，因此还应该继续从$y'+g[x'][y'] + 1$向右枚举。向下的方向也同理。
AC代码如下：
1 class Solution { 2 public: 3 int minimumVisitedCells(vector<vector<int>>& grid) { 4 int n = grid.size(), m = grid[0].size(); 5 vector<vector<int>> dist(n, vector<int>(m, 0x3f3f3f3f)); 6 dist[0][0] = 0; 7 queue<pair<int, int>> q({{0, 0}}); 8 while (!q.empty()) { 9 int x = q.front().first, y = q.front().second; 10 q.pop(); 11 // 向下枚举 12 for (int i = x + 1; i <= grid[x][y] + x; i++) { 13 if (i >= n) break; 14 if (dist[i][y] > dist[x][y] + 1) { 15 dist[i][y] = dist[x][y] + 1; 16 q.push({i, y}); 17 } 18 else if (dist[i][y] < dist[x][y] + 1) { 19 if (grid[x][y] + x > grid[i][y] + i) i += grid[i][y]; // 从(x,y)能比(i,y)走到更下的地方 20 else break; 21 } 22 } 23 // 向右枚举 24 for (int j = y + 1; j <= grid[x][y] + y; j++) { 25 if (j >= m) break; 26 if (dist[x][j] > dist[x][y] + 1) { 27 dist[x][j] = dist[x][y] + 1; 28 q.push({x, j}); 29 } 30 else if (dist[x][j] < dist[x][y] + 1) { 31 if (grid[x][y] + y > grid[x][j] + j) j += grid[x][j]; // 从(x,y)能比(x,j)走到更右的地方 32 else break; 33 } 34 } 35 } 36 return dist[n - 1][m - 1] == 0x3f3f3f3f ? -1 : dist[n - 1][m - 1] + 1; 37 } 38 };
对于边数很多的情况，可以再参考Minimum Reverse Operations中用并查集和平衡树的做法。
先简单给出平衡树的思路。本质上就是根据bfs中更新过的节点不会再被更新这个性质，我们在枚举相邻节点时可以把那些已经更新过的节点跳过。做法就是开个平衡树，然后找到能更新的范围，对这个范围内还存在未更新过的节点进行更新，并将其从平衡树中删除，这样下次就不会再枚举到这个已更新的节点了。而本题是二维的情况，因此可以给每一行开一个平衡树，一共$n$个；每一列开一个平衡树，一共$m$个。当更新了位置$(x',y')$时，不管是哪个方向，在维护第$x'$行的平衡树中删除元素$y'$，在维护第$y'$列的平衡树中删除元素$x'$。
AC代码如下，时间复杂度为$O(nm \cdot (\log{n} + \log{m}))$：
1 class Solution { 2 public: 3 int INF = 1e9; 4 5 int minimumVisitedCells(vector<vector<int>>& grid) { 6 int n = grid.size(), m = grid[0].size(); 7 vector<set<int>> st1(n), st2(m); 8 for (int i = 0; i < n; i++) { 9 for (int j = 0; j < m; j++) { 10 st1[i].insert(j); 11 } 12 st1[i].insert({-INF, INF}); // 插入哨兵，保证每次都能二分出结果 13 } 14 for (int i = 0; i < m; i++) { 15 for (int j = 0; j < n; j++) { 16 st2[i].insert(j); 17 } 18 st2[i].insert({-INF, INF}); 19 } 20 vector<vector<int>> dist(n, vector<int>(m, 0x3f3f3f3f)); 21 dist[0][0] = 1; 22 st1[0].erase(0), st2[0].erase(0); // (0,0)已经更新过了，因此在维护第0行的平衡树中删除0，在维护第0列的平衡树中删除0 23 queue<pair<int, int>> q({{0, 0}}); 24 while (!q.empty()) { 25 auto t = q.front(); 26 q.pop(); 27 auto l = st1[t.first].lower_bound(t.second + 1), r = st1[t.first].upper_bound(t.second + grid[t.first][t.second]); 28 // 向右枚举 29 while (l != r) { 30 dist[t.first][*l] = dist[t.first][t.second] + 1; 31 q.push({t.first, *l}); // 更新了位置(t.first, l) 32 st2[*l].erase(t.first); // 在维护第l列的平衡树中删除t.first 33 l = st1[t.first].erase(l); // 在维护第t.first行的平衡树中删除l 34 } 35 l = st2[t.second].lower_bound(t.first + 1), r = st2[t.second].upper_bound(t.first + grid[t.first][t.second]); 36 while (l != r) { 37 dist[*l][t.second] = dist[t.first][t.second] + 1; 38 q.push({*l, t.second}); // 更新了位置(l, t.second) 39 st1[*l].erase(t.second); // 在维护第l行的平衡树中删除t.second 40 l = st2[t.second].erase(l); // 在维护第t.second列的平衡树中删除l 41 } 42 } 43 return dist[n - 1][m - 1] == 0x3f3f3f3f ? -1 : dist[n - 1][m - 1]; 44 } 45 };
并查集就是维护删除元素的连通性，每次直接向右找到第一个还没被删除的位置，然后删除这个位置再维护连通性。也需要对每一行和每一列都开并查集维护。当更新了位置$(x',y')$时，需要在维护第$x'$行的并查集中将$y'$所在的集合合并到$y'+1$所在的集合；在维护第$y'$列的并查集中将$x'$所在的集合合并到$x'+1$所在的集合。
AC代码如下，时间复杂度为$O(nm)$：
1 class Solution { 2 public: 3 int minimumVisitedCells(vector<vector<int>>& grid) { 4 int n = grid.size(), m = grid[0].size(); 5 vector<vector<int>> fa1(n, vector<int>(m + 1)), fa2(m, vector<int>(n + 1)); 6 for (int i = 0; i < n; i++) { 7 for (int j = 0; j <= m; j++) { 8 fa1[i][j] = j; 9 } 10 } 11 for (int i = 0; i < m; i++) { 12 for (int j = 0; j <= n; j++) { 13 fa2[i][j] = j; 14 } 15 } 16 vector<vector<int>> dist(n, vector<int>(m, 0x3f3f3f3f)); 17 dist[0][0] = 1; 18 fa1[0][0] = fa2[0][0] = 1; 19 queue<pair<int, int>> q({{0, 0}}); 20 function<int(vector<int>&, int)> find = [&](vector<int> &fa, int x) { 21 return fa[x] == x ? fa[x] : fa[x] = find(fa, fa[x]); 22 }; 23 while (!q.empty()) { 24 auto t = q.front(); 25 q.pop(); 26 int y = find(fa1[t.first], t.second + 1); 27 while (y <= t.second + grid[t.first][t.second] && y < m) { 28 dist[t.first][y] = dist[t.first][t.second] + 1; 29 q.push({t.first, y}); 30 fa1[t.first][y] = find(fa1[t.first], y + 1); 31 fa2[y][t.first] = find(fa2[y], t.first + 1); 32 y = find(fa1[t.first], y + 1); 33 } 34 int x = find(fa2[t.second], t.first + 1); 35 while (x <= t.first + grid[t.first][t.second] && x < n) { 36 dist[x][t.second] = dist[t.first][t.second] + 1; 37 q.push({x, t.second}); 38 fa2[t.second][x] = find(fa2[t.second], x + 1); 39 fa1[x][t.second] = find(fa1[x], t.second + 1); 40 x = find(fa2[t.second], x + 1); 41 } 42 } 43 return dist[n - 1][m - 1] == 0x3f3f3f3f ? -1 : dist[n - 1][m - 1]; 44 } 45 };
参考资料
暴力 BFS | BFS + 并查集 | BFS + 平衡树 | 线段树：https://leetcode.cn/problems/minimum-number-of-visited-cells-in-a-grid/solution/bfs-bing-cha-ji-by-xjliang-3ito/