本文主要是介绍网格bfs，LeetCode 2684. 矩阵中移动的最大次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
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、原题链接
2684. 矩阵中移动的最大次数
二、解题报告
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] *= -1for j in range(n - 1):for i, row in enumerate(g):if row[j] > 0:continuefor k in i - 1, i, i + 1:if 0 <= k < m and g[k][j + 1] > -row[j]:g[k][j + 1] *= -1if all(row[j + 1] > 0 for row in g):return jreturn n - 1这篇关于网格bfs，LeetCode 2684. 矩阵中移动的最大次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
