当前位置：首页 > article >正文

矩阵中移动的最大次数

article 2025/1/21 14:04:19

文章目录

所属专栏:BFS算法

题目链接
在这里插入图片描述

思路如下：
1.首先我们需要从第一列开始遍历，寻找每一个都能够满足条件的位置，将它插入到数组里面
2.第一列遍历完了后我们先判断第一列的数是否都满足条件插入到数组里面，如果数组为空，那么全部不满足条件，这个时候我们就可以返回0
3.如果不为空那么就继续从第一列开始向第二列遍历，这个时候我们需要清楚数组里面上一轮的能满足条件的数，便于下一次遍历交换

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int>q1,q2;
        for(int i = 0;i<m;i++)
        q1.push_back(i);
        for(int j = 1;j<n;j++)
        {
            q2.clear();
            for(auto i:q1)
            {
                for(int i2 = i-1;i2<=i+1;i2++)
                {
                    if(i2>=0&&i2<m&&grid[i2][j]>grid[i][j-1])
                    q2.push_back(i2);
                }
            }
            swap(q1,q2);
            if(q1.empty())
            return j-1;
        }
        return n-1;
    }
};