矩阵中移动的最大次数

所属专栏: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;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

代码解读：
1.为了能让第每次遍历完就开始遍历下一次的行数下标，我们需要再创建一个数组，把q2与q1交换
2.然后清除q2里面的内容，这样q1就是第一次遍历满足条件的下标，这样循环就可以达到依次遍历的目的