题解 | #矩阵最长递增路径#

1.DFS

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    void dfs(vector<vector<int>>& matrix,int &count,vector<vector<int>>& visited,int i,int j,int n,int m,int &max)
    {
        visited[i][j] = 1;
        count++;
        if(max < count)
            max = count;
        if(i-1>=0 && visited[i-1][j] == 0 && matrix[i-1][j] > matrix[i][j])
            dfs(matrix, count, visited, i-1, j, n, m,max);
        if(i+1<n && visited[i+1][j] == 0 && matrix[i+1][j] > matrix[i][j])
            dfs(matrix, count, visited, i+1, j, n, m,max);
        if(j-1>=0 && visited[i][j-1] == 0 && matrix[i][j-1] > matrix[i][j])
            dfs(matrix, count, visited, i, j-1, n, m,max);
        if(j+1<m && visited[i][j+1] == 0 && matrix[i][j+1] > matrix[i][j])
            dfs(matrix, count, visited, i, j+1, n, m,max);
        visited[i][j] = 0;
        count--;
    }
    int solve(vector<vector<int> >& matrix) {
        // write code here
        int count = 0;
        int n = matrix.size();
        int m = matrix[0].size();
        int max = 0;
        vector<vector<int>> visited(n,vector<int>(m,0));
        for(int i = 0;i<n;++i)
        {
            for(int j = 0;j<m;++j)
            {
                dfs(matrix, count, visited, i, j, n, m, max);
            }
        }
        return max;
    }
};

2.BFS

思路：

我们可以将矩阵看成是一个有向图，一个元素到另一个元素递增，代表有向图的箭头。这样我们可以根据有向图的出度入度找到最长的路径，且这个路径在矩阵中就是递增的。

具体做法：

• step 1：计算每个节点（单元格）所对应的出度（符合边界条件且递增），对于作为边界条件的单元格，它的值比所有的相邻单元格的值都要大，因此作为边界条件的单元格的出度都为0。利用一个二维矩阵记录每个单元格的出度
• step 2：利用拓扑排序的思想，从所有出度为0的单元格开始进行广度优先搜索。
• step 3：借助队列来广度优先搜索，队列中每次加入出度为0的点，即路径最远点，每次从A点到B点，便将A点出度减一。
• step 4：每次搜索都会遍历当前层的所有单元格，更新其余单元格的出度，并将出度变为0的单元格加入下一层搜索。
• step 5：当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度，因为bfs的层数就是路径增长的层数。

#include <queue>
#include <vector>
class Solution {
public:
    int solve(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size();
        int m = matrix[0].size();
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};//记录四个方向
        vector<vector<int>> outdegrees(n,vector<int>(m,0));//记录每个单元的出度
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                for(int k = 0;k<4;k++)
                {
                    int nexti = i + dirs[k][0];
                    int nextj = j + dirs[k][1];
                    if(nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] > matrix[i][j])
                    {
                        outdegrees[i][j]++;//符合条件，记录出度
                    }
                } 
            }
        }
        queue<pair<int,int>> q;
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                //出度为0的数就是周围的数都比它的小的那些数
                if(outdegrees[i][j] == 0)
                    q.push({i,j});//找到出度为0的入队列
            }
        }
        int res = 0;
        //逆向思维：从路径最远点出发，找到路径的头，也就是出度为0的点,途中记录该路径的长度
        while(!q.empty())
        {
            res++;
            int size = q.size();
            for(int x = 0;x < size ; x++)
            {
                pair<int,int> temp = q.front();
                q.pop();
                int i = temp.first;
                int j = temp.second;
                //四个方向
                for(int k = 0;k<4;++k)
                {
                    int nexti = i + dirs[k][0];
                    int nextj = j + dirs[k][1];
                    //逆向搜索，所以下一步是小于
                    if(nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] < matrix[i][j])
                    {
                        //符合条件，出度递减
                        outdegrees[nexti][nextj]--;
                        if(outdegrees[nexti][nextj] == 0)
                            q.push({nexti,nextj});
                    }
                }
            }
        }
        return res;

    }
};