Leetcode 329 矩阵中的最长递增路径

题目链接

题目描述

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：

输入: nums = [

[9,9,4],

[6,6,8],

[2,1,1]

]

输出: 4

解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2：

输入: nums =

[

[3,4,5],

[3,2,6],

[2,2,1]

]

输出: 4

解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

解 大概是BFS

题目不给数据范围就很离谱。不允许在对角线方向上移动就很废话，误以为不能经过对角线上的点wa了一发。

感觉排序有点麻烦就没排序直接莽，直接遍历整个数组找没被搜索过的点。

找到一个没有搜索过的点时，把它作为起点，并把该点的ans记为1，判断它能到达的点(位于上下左右且大于该点)，如果有则把能到达的点ans记为2(1+1)，并放入队列。之后从队列中取出点并判断取出的点的ans+1是否大于它能到达的点的ans，如果大于则更新该点并放入队列。

做完以后看了题解发现还是拓扑排序(转化为有向图按出度排序)比较香，这种题目果然还是应该当图做orz。

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int column=matrix[0].size(),row=matrix.size();
        int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
        vector<vector<int>> ans(row,vector<int>(column,0));
        queue<pair<int,int>> next;
        for(int i=0;i<row;i++)
        {
            for(int j=0;j<column;j++)
            {
                if(!ans[i][j])
                {
                    ans[i][j]=1;
                    next.push({i,j});
                }
                while(!next.empty())
                {
                    int x=next.front().first,y=next.front().second;
                    next.pop();
                    for(int k=0;k<4;k++)
                    {
                        if(x+dir[k][0]>=0&&x+dir[k][0]<row&&y+dir[k][1]>=0&&y+dir[k][1]<column)
                        {
                            if(matrix[x+dir[k][0]][y+dir[k][1]]>matrix[x][y])
                            {
                                if(ans[x][y]+1>ans[x+dir[k][0]][y+dir[k][1]])
                                {
                                    ans[x+dir[k][0]][y+dir[k][1]]=ans[x][y]+1;
                                    next.push({x+dir[k][0],y+dir[k][1]});
                                }
                            }
                        }
                    }
                }
            }
        }
        int maxans=1;
        for(int i=0;i<row;i++)
            for(int j=0;j<column;j++) maxans=max(maxans,ans[i][j]);
        return maxans;
    }
};