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/