网格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] *= -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