一、题目
1、题目描述
给你一个下标从 0 开始、大小为
m x n的矩阵grid，矩阵由若干 正 整数组成。你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历
grid：
- 从单元格
(row, col)可以移动到(row - 1, col + 1)、(row, col + 1)和(row + 1, col + 1)三个单元格中任一满足值 严格 大于当前单元格的单元格。返回你在矩阵中能够 移动 的 最大 次数。
2、接口描述
cpp
class Solution {
public:
int maxMoves(vector<vector<int>>& grid) {
}
};python3
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:3、原题链接
二、解题报告
1、思路分析
我们将第一列的位置入队，然后在网格上进行bfs
对于每个当前位置可以抵达的位置，我们就将其入队，然后记得标记
2、复杂度
时间复杂度： O(mn)空间复杂度：O(mn)
3、代码详解
cpp
class Solution {
public:
typedef pair<int, int> PII;
static constexpr int dst[3][2] = {{-1, 1}, {0, 1}, {1, 1}};
int maxMoves(vector<vector<int>>& g) {
queue<PII> q;
int m = g.size(), n = g[0].size(), ret = 0;
vector<vector<bool>> vis(m, vector<bool>(n));
for(int i = 0; i < m; i++) q.emplace(i, 0);
while(q.size()){
for(int i = 0, ed = q.size(); i < ed; i++){
auto [x, y] = q.front(); q.pop();
for(int j = 0, nx, ny; j < 3; j++){
nx = x + dst[j][0], ny = y + dst[j][1];
if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if(vis[nx][ny] || g[x][y] >= g[nx][ny]) continue;
q.emplace(nx, ny), vis[nx][ny] = 1;
}
}
ret += !q.empty();
}
return ret;
}
};python3
class Solution:
def maxMoves(self, g: List[List[int]]) -> int:
m, n = len(g), len(g[0])
for i in range(m):
g[i][0] *= -1
for j in range(n - 1):
for i, row in enumerate(g):
if row[j] > 0:
continue
for k in i - 1, i, i + 1:
if 0 <= k < m and g[k][j + 1] > -row[j]:
g[k][j + 1] *= -1
if all(row[j + 1] > 0 for row in g):
return j
return n - 1
