题解 | 矩阵最长递增路径

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */

    int res=0;
    vector< vector<int>> visted;  //0表示没有访问，其他表示长度

    int solve(vector<vector<int> >& matrix) {
        visted.resize(matrix.size(), vector<int>(matrix[0].size(), 0));  //先把大小确定了，再填值；
        for(int i=0; i<matrix.size(); i++){
            for(int j=0; j<matrix[0].size(); j++){
                dfs(matrix, i, j, 0, -1);
            }
        }
        
        return res;
    }

    void dfs(vector< vector<int> >& matrix, int i, int j, int count, int pre){
        if(i >= matrix.size() || i<0 || j<0 || j>=matrix[0].size() || pre >= matrix[i][j]){   //超出了界限 or not increased
            return;
        }

        if(visted[i][j] != 0){return;}  //访问过了；

        visted[i][j] = count+1;
        res = max(res, count+1);  //refresh

        dfs(matrix, i-1, j, count+1, matrix[i][j]);  //up
        dfs(matrix, i+1, j, count+1, matrix[i][j]);  //down
        dfs(matrix, i, j+1, count+1, matrix[i][j]);  //right
        dfs(matrix, i, j-1, count+1, matrix[i][j]);  //left

        visted[i][j] = 0;

        return;
    }
};