题解 | 矩阵最长递增路径

#include <algorithm>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int ans=1;
    void Process(vector<vector<int> >& matrix,vector<vector<int> >& dp){
        int m,n;
        m = matrix.size();
        n = matrix[0].size();
        bool changed = true;
        while(changed){
            changed = false;
            for(int i=0;i<m;i++) for(int j=0;j<n;j++){
                vector<int> candidate={1};
                
                if(i-1>=0 && matrix[i-1][j]<matrix[i][j]) candidate.push_back(dp[i-1][j]+1);
                if(i+1<=m-1 && matrix[i+1][j]<matrix[i][j]) candidate.push_back(dp[i+1][j]+1);
                if(j-1>=0 && matrix[i][j-1]<matrix[i][j]) candidate.push_back(dp[i][j-1]+1);
                if(j+1<=n-1 && matrix[i][j+1]<matrix[i][j]) candidate.push_back(dp[i][j+1]+1);
                auto it = max_element(candidate.begin(), candidate.end());
                if(it!=candidate.end()) {
                    if(dp[i][j]<*it){
                        dp[i][j] = *it;
                        changed=true;
                        ans = ans>dp[i][j] ? ans:dp[i][j];
                    }
                }
            }

        }
    }
    int solve(vector<vector<int>>& matrix) {
        // write code here
        if(matrix.empty()) return 0;
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),1));
        Process(matrix,dp);
        return ans;
    }
};