题解 | 矩阵最长递增路径

#include<vector>
using namespace std;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int solve(vector<vector<int> >& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int row = matrix.size();
        int col = matrix[0].size();
        int* path = new int[row * col];

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                path[i * col + j] = matrix[i][j];
            }
        }
        int* rec = new int[row * col]();
        int a=0;
        bool is = false;
        int max=0;
    int total=0;
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            rec[i*col+j]=1;
            s(i,j,path,rec,&total,col,row,&max);
            rec[i*col+j]=0;
        }
    }return max+1;
    }void s(int x,int y,int* path,int* rec,int* total,int col,int row,int* max){
    //rec[x*col+y]=1;
    if(x>=1){
        if(path[(x-1)*col+y]>path[x*col+y]&&rec[(x-1)*col+y]==0){
            rec[(x-1)*col+y]=1;
            (*total)++;
            s(x-1,y,path,rec,total,col,row,max);
            (*total)--;
            rec[(x-1)*col+y]=0;
        }
    }if(x+1<row){
        if(path[(x+1)*col+y]>path[x*col+y]&&rec[(x+1)*col+y]==0){
            rec[(x+1)*col+y]=1;
            (*total)++;
            s(x+1,y,path,rec,total,col,row,max);
            (*total)--;
            rec[(x+1)*col+y]=0;
        }
    }if(y>=1){
        if(path[x*col+y-1]>path[x*col+y]&&rec[x*col+y-1]==0){
            rec[x*col+y-1]=1;
            (*total)++;
            s(x,y-1,path,rec,total,col,row,max);
            (*total)--;
            rec[x*col+y-1]=0;
        }
    }if(y+1<col){
        if(path[x*col+y+1]>path[x*col+y]&&rec[x*col+y+1]==0){
            rec[x*col+y+1]=1;
            (*total)++;
            s(x,y+1,path,rec,total,col,row,max);
            (*total)--;
            rec[x*col+y+1]=0;
        }
    }if(*total>*max){
        (*max)=(*total);
    }
}
};