矩阵最长递增路径

#define N 1000

static int __memo[N][N]; // 缓存记忆体

// ======================== function prototype ========================
int depth_first_search_with_memorization_algorithm(int** matrix,
                                                   const int m,
                                                   const int n,
                                                   int x, int y);

int solve(int** matrix, int matrixRowLen, int* matrixColLen ) {
  const int m = matrixRowLen, n = *matrixColLen;
  memset(__memo, -1, sizeof __memo);
  
  int x, y, ans = 0;
  for (y = 0; y < m; ++y)
    for (x = 0; x < n; ++x)
      ans = fmax(ans, depth_first_search_with_memorization_algorithm(matrix, m, n, x, y));
  
  return ans;
}

int depth_first_search_with_memorization_algorithm(int** matrix,
                                                   const int m,
                                                   const int n,
                                                   int x, int y) {
  
  static const int dirs[] = { 0, -1, 0, 1, 0 };
  
  if (__memo[y][x] != -1) return __memo[y][x];
  
  int i, nx, ny, longest = 0;
  for (i = 0; i < 4; ++i) {
    nx = x + *(dirs + i), ny = y + *(dirs + i + 1);
    if (nx < 0 || nx == n || ny < 0 || ny == m ||
        *(*(matrix + y) + x) >= *(*(matrix + ny) + nx))
      continue;
    longest = fmax(longest, depth_first_search_with_memorization_algorithm(matrix, m, n, nx, ny));
  }
  
  return __memo[y][x] = 1 + longest;
}

import java.util.*;


public class Solution {
    
    private int res = 0;
    
    public int solve (int[][] matrix) {
        for (int i = 0;i < matrix.length;i++) {
            for (int j = 0;j < matrix[0].length;j++) {
                dfs(matrix, i, j, 0, -1);
            }
        }
        return res;
    }
    
    public void dfs(int[][] matrix, int x, int y, int tmp, int prev) {
        if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= prev) {
            res = Math.max(res, tmp);
            return;
        }
        dfs(matrix, x+1, y, tmp+1, matrix[x][y]);
        dfs(matrix, x-1, y, tmp+1, matrix[x][y]);
        dfs(matrix, x, y-1, tmp+1, matrix[x][y]);
        dfs(matrix, x, y+1, tmp+1, matrix[x][y]);
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int solve(vector<vector<int> >& matrix) {
        // 时间复杂度O(MN)，空间复杂度O(MN)
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                vector<int> path;
                dfs(matrix, i, j, path);
            }
        }
        return res;
    }
    void dfs(vector<vector<int>> &matrix, int i, int j, vector<int> &path) {
        if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size() || 
            (!path.empty() && matrix[i][j] <= path.back())) {
            res = res > path.size() ? res : path.size();
            return;
        }
        path.push_back(matrix[i][j]);
        dfs(matrix, i - 1, j, path);
        dfs(matrix, i + 1, j, path);
        dfs(matrix, i, j - 1, path);
        dfs(matrix, i, j + 1, path);
        path.pop_back();
    }
    int res = 0;
};

import java.util.*;


public class Solution {
    private int maxLen = 1;
    private int row;
    private int column;
    private int[][] dp;
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    public int solve (int[][] matrix) {
        // write code here
//        既然是递增的，那走的路径应该就不会是重复的格子了
        if(matrix == null || matrix.length == 0){
            return 0;
        }
        row = matrix.length;
        column = matrix[0].length;
        if(row == 1 && column == 1){
            return 1;
        }
        //维护一个dp 来记录以此为起点的 maxLen
        dp = new int[row][column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                dfs(matrix, i, j, 1);
                dp[i][j] = maxLen;
                maxLen = 1;
            }
        }
        //返回dp的最大值
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if(dp[i][j] > maxLen){
                    maxLen = dp[i][j];
                }
            }
        }
        return maxLen;
    }

    public void dfs(int[][] matrix, int x, int y, int len) {
        if (x < 0 || x >= row || y < 0 || y >= column) {
            return;
        }
        //上
        if(y > 0 && matrix[x][y] < matrix[x][y - 1]){
            //如果这里曾经来过
            if(dp[x][y - 1] != 0){
                maxLen = Math.max(maxLen, len + dp[x][y - 1]);
            }else{
                maxLen = Math.max(maxLen, len + 1);
                dfs(matrix, x, y - 1, len + 1);
            }
        }
        //下
        if(y + 1 < column && matrix[x][y] < matrix[x][y + 1]){
            //如果这里曾经来过
            if(dp[x][y + 1] != 0){
                maxLen = Math.max(maxLen, len + dp[x][y + 1]);
            }else{
                maxLen = Math.max(maxLen, len + 1);
                dfs(matrix, x, y + 1, len + 1);
            }
        }
        //左
        if(x > 0 && matrix[x][y] < matrix[x - 1][y]){
            //如果这里曾经来过
            if(dp[x - 1][y] != 0){
                maxLen = Math.max(maxLen, len + dp[x - 1][y]);
            }else{
                maxLen = Math.max(maxLen, len + 1);
                dfs(matrix, x - 1, y, len + 1);
            }
        }
        //右
        if(x + 1 < row && matrix[x][y] < matrix[x + 1][y]){
            //如果这里曾经来过
            if(dp[x + 1][y] != 0){
                maxLen = Math.max(maxLen, len + dp[x + 1][y]);
            }else{
                maxLen = Math.max(maxLen, len + 1);
                dfs(matrix, x + 1, y, len + 1);
            }
        }
    }
}

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

import java.util.*;


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

    public int solve (int[][] matrix) {
        // write code here
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                findPath(matrix, i, j, 0, -1);
            }
        }
        return maxPath;
    }

    void findPath (int[][] matrix, int i, int j, int num, int lastNum) {
        if (i < 0 || i >= matrix.length || j < 0
                || j>= matrix[0].length || matrix[i][j] <= lastNum) {
            maxPath = Math.max(maxPath, num);
            return;
        }
        ++ num;
        findPath(matrix, i + 1, j, num, matrix[i][j]);
        findPath(matrix, i, j + 1, num, matrix[i][j]);
        findPath(matrix, i - 1, j, num, matrix[i][j]);
        findPath(matrix, i, j - 1, num, matrix[i][j]);
    }
}

class Solution {
private:
    int res = 0;
    int dfs(vector<vector<int> >& matrix, int x, int y, int pre){
        if(pre >= matrix[x][y]){
            return 0;
        }
        int mx = 0;
        if(x + 1 < matrix.size()){
            mx = max(mx, dfs(matrix, x + 1, y, matrix[x][y]));
        }
        if(y + 1 < matrix.size()){
            mx = max(mx, dfs(matrix, x , y + 1, matrix[x][y]));
        }
        if(x - 1 >= 0){
            mx = max(mx, dfs(matrix, x - 1, y, matrix[x][y]));
        }
        if(y - 1 >= 0){
            mx = max(mx, dfs(matrix, x, y - 1, matrix[x][y]));
        }
        return mx + 1;
    }

public:
    int solve(vector<vector<int> >& matrix) {
        if(!matrix.size()) return res;
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                res = max(res, dfs(matrix, i, j, -1));
            }
        }
        return res;
    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型 臭长虫代码
     */
    public int solve (int[][] matrix) {
        // write code here
        int max = 0;
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] cur = new int[row][col];
        Queue<int[]> qu = new ArrayDeque<>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (cur[i][j] == 0) {
                    int[] w = new int[2];
                    cur[i][j] = 1;
                    w[0] = i;
                    w[1] = j;
                    qu.add(w);
                    while (!qu.isEmpty()) {
                        int[] k = qu.poll();
                        int m = k[0];
                        int n = k[1];
                        if (max < cur[m][n]) {
                            max = cur[m][n];
                        }
                        if (m > 0 && matrix[m][n] < matrix[m - 1][n] &&
                                cur[m - 1][n] <= cur[m][n]) { //往上走
                            cur[m - 1][n] = cur[m][n] + 1;
                            int[] q = new int[2];
                            q[0] = m - 1;
                            q[1] = n;
                            qu.add(q);
                        }
                        if (m < matrix.length - 1 && matrix[m][n] < matrix[m + 1][n] &&
                                cur[m + 1][n] <= cur[m][n]) { //往下走
                            cur[m + 1][n] = cur[m][n] + 1;
                            int[] q = new int[2];
                            q[0] = m + 1;
                            q[1] = n;
                            qu.add(q);
                        }
                        if (n > 0 && matrix[m][n] < matrix[m][n - 1] &&
                                cur[m][n - 1] <= cur[m][n]) { //往左走
                            cur[m][n - 1] = cur[m][n] + 1;
                            int[] q = new int[2];
                            q[0] = m;
                            q[1] = n - 1;
                            qu.add(q);
                        }
                        if (n < matrix[0].length - 1 && matrix[m][n] < matrix[m][n + 1] &&
                                cur[m][n + 1] <= cur[m][n]) { //往右走
                            cur[m][n + 1] = cur[m][n] + 1;
                            int[] q = new int[2];
                            q[0] = m;
                            q[1] = n + 1;
                            qu.add(q);
                        }
                    }
                }
            }
        }
        return max;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    int max =0;
    int m;
    int n;
    int[][] matrix;
    public int solve (int[][] matrix) {
        this.matrix = matrix;
        if(matrix==null||matrix.length==0||matrix[0].length==0) return 0;
        this.m = matrix.length;
        this.n = matrix[0].length;
        for(int i=0;i<m;i++){
            for(int j =0;j<n;j++){
                backtraking(i,j,-1,0);
            }
        }
        return max;
        
    }

    public void backtraking(int i,int j,int pre,int len){
        if(i<0||i>=m||j<0||j>=n||matrix[i][j]<=pre){
            max = Math.max(max,len);
            return;
        }
        int temp = matrix[i][j];
        matrix[i][j]=-1;
        backtraking(i-1,j,temp,len+1);
        backtraking(i+1,j,temp,len+1);
        backtraking(i,j-1,temp,len+1);
        backtraking(i,j+1,temp,len+1);
        matrix[i][j]=temp;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 递增路径的最大长度
# @param matrix int整型二维数组 描述矩阵的每个数
# @return int整型
#
class Solution:
    def solve(self , mat: List[List[int]]) -> int:
        # write code here
        dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        def dfs(i, j):
            if memo[i][j] > 0 : return memo[i][j]
            memo[i][j] = 1
            for dir in dirs:
                x, y = i + dir[0], j + dir[1]
                if x < 0&nbs***bsp;x >= len(mat)&nbs***bsp;y < 0&nbs***bsp;y >= len(mat[0])&nbs***bsp;mat[x][y] <= mat[i][j]: continue
                memo[i][j] = max(memo[i][j], dfs(x, y) + 1)
            return memo[i][j]
        m, n, ans = len(mat), len(mat[0]), 0
        memo = [[0] * n for _ in range(m)] 
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                ans = max(ans, dfs(i, j))
        return ans

class Solution:
    def solve(self , matrix: List[List[int]]) -> int:
        # write code here
        '''
        使用record记录以某个单元格为 起点 的最大路径.
        '''
        def dfs(row, col, record):
            if record[row][col] != 0: return record[row][col]
            record[row][col] = 1 # 当前单元格标致为1.
            up = down = left = right = 1

            if row - 1 >= 0 and matrix[row - 1][col] > matrix[row][col]:
                up = dfs(row - 1, col, record) + 1    # 上
            if row + 1 < len(matrix) and matrix[row + 1][col] > matrix[row][col]:
                down = dfs(row + 1, col, record) + 1  # 下
            if col - 1 >= 0 and matrix[row][col - 1] > matrix[row][col]:
                left = dfs(row, col - 1, record) + 1  # 左
            if col + 1 < len(matrix[0]) and matrix[row][col + 1] > matrix[row][col]:
                right = dfs(row, col + 1, record) + 1 # 右

            cur_longest = max(up, down, left, right)
            record[row][col] = cur_longest
            return cur_longest

        longest = 1
        record = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                longest = max(longest, dfs(row, col, record))
        return longest

class Solution {
public:
    int solve(vector<vector<int> >& matrix) {
        if(matrix.empty()) return 0;
        int maxstep = 1;
        for(int i=0;i<matrix.size();++i){
            for(int j=0;j<matrix[0].size();++j){
                maxstep = max(dfs(matrix,i,j), maxstep);
            }
        }
        return maxstep;
    }
    
    int dfs(vector<vector<int>>& matrix, int i, int j){
        int maxstep = 1;
        if(i>0 && matrix[i][j]>matrix[i-1][j]) 
            maxstep = max(dfs(matrix,i-1,j) + 1,maxstep);
        if(i<matrix.size()-1 && matrix[i][j]>matrix[i+1][j])
            maxstep = max(dfs(matrix,i+1,j) + 1,maxstep);
        if(j>0 && matrix[i][j]>matrix[i][j-1])
            maxstep = max(dfs(matrix,i,j-1) + 1,maxstep);
        if(j<matrix[0].size()-1 && matrix[i][j]>matrix[i][j+1])
            maxstep = max(dfs(matrix,i,j+1) + 1,maxstep);
        return maxstep ;
    }
};

#include <algorithm>
#include <vector>
class Solution {
  public:
     vector<int>ans;
    void dfs(vector<vector<int> >& matrix, int mx, int i, int j) {
        int len = matrix.size();
        int len1 = matrix[0].size();
        ans.push_back(mx);
        int temp = matrix[i][j];
        if (i - 1 >= 0 && matrix[i - 1][j] > temp) {
            dfs(matrix, mx + 1, i - 1, j);
        }
        if (i + 1 < len && matrix[i + 1][j] > temp) {
            dfs(matrix, mx + 1, i + 1, j);
        }
        if (j - 1 >= 0 && matrix[i][j - 1] > temp) {
            dfs(matrix, mx + 1, i, j - 1);
        }
        if (j + 1 < len1 && matrix[i][j + 1] > temp) {
            dfs(matrix, mx + 1, i, j + 1);
        }
    }
    int solve(vector<vector<int> >& matrix) {
        int len = matrix.size();
        int len1 = matrix[0].size();
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len1; j++) {
                int mx = 0;
                dfs(matrix, mx, i, j);
            }
        }
        return *max_element(ans.begin(), ans.end())+1;
    }
};

#define max(a, b) (a>b ? a : b)
int run(int** matrix, int matrixRowLen, int matrixColLen, int row, int col, int lastMVal) {    
    int res=0;
    if(matrix[row][col]<=lastMVal)
        return 0;
    if(row<matrixRowLen-1) 
        res = max(res, run(matrix, matrixRowLen, matrixColLen, row+1, col, matrix[row][col]));
    if(row>0) 
        res = max(res, run(matrix, matrixRowLen, matrixColLen, row-1, col, matrix[row][col]));
    if(col<matrixColLen-1) 
        res = max(res, run(matrix, matrixRowLen, matrixColLen, row, col+1, matrix[row][col]));
    if(col>0) 
        res = max(res, run(matrix, matrixRowLen, matrixColLen, row, col-1, matrix[row][col]));   
    return res+1;
}

int solve(int** matrix, int matrixRowLen, int* matrixColLen ) {
    int  res=0, i, j;
    for(i=0; i<matrixRowLen; i++) 
        for(j=0; j<*matrixColLen; j++) 
            res = max(res, run(matrix, matrixRowLen, *matrixColLen, i, j, -1)); 
    return res;
}

int res=0;
public int solve (int[][] matrix) {
    // write code here
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[i].length;j++){
            dfs(matrix , i ,j ,0 ,-1);
        }
    }
    return res;
}

public void dfs(int[][] matrix ,int m ,int n ,int cnt ,int val){
    // 满足m,n均在范围内，且当前值大于上一步的值，才可以继续累加（走回头路不满足递增，会马上被return掉）
    if(m<0 || m>=matrix.length || n<0 || n>=matrix[0].length || matrix[m][n]<=val){
        res=Math.max(res ,cnt);
        return;
    }
    cnt++;
    dfs(matrix ,m+1 ,n ,cnt ,matrix[m][n]);
    dfs(matrix ,m-1 ,n ,cnt ,matrix[m][n]);
    dfs(matrix ,m ,n+1 ,cnt ,matrix[m][n]);
    dfs(matrix ,m ,n-1 ,cnt ,matrix[m][n]);
}

class Solution {
  public:
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n, m;
    int solve(vector<vector<int> >& matrix) {
        // 正向dp，比官方答案耗时多20%。原因在于新路径的后半部分“并入”之后会重写后半部分的dp(相当于该路径的所有dp都要更新)，而反向dp仅更新前半部分。
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        int res = 0;
        n = matrix.size();
        m = matrix[0].size();

        vector<vector<int>> dp (n, vector<int> (m));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                dfs(matrix, dp, i, j);
            }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                res = max(res, dp[i][j]);
            }

        return res + 1;
    }

    void dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int i, int j) {
        // 如果增参以int &res的话，耗时会变多为40%

        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] && dp[i][j] + 1 > dp[nexti][nextj]) {
                dp[nexti][nextj] = dp[i][j] + 1;
                dfs(matrix, dp, nexti, nextj);
            }
        }
    }
};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
 */
function solve( matrix ) {
    // write code here
    let dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    let n = matrix.length;
    let m = matrix[0].length;
    let dp = new Array(m+1).fill(0).map(()=> new Array(n+1).fill(0));
    function dfs(i,j){
        if(dp[i][j]!=0){
            return dp[i][j];
        }
        dp[i][j]++;
        for(let k=0;k<4;k++){
            let nexti = i + dirs[k][0];
            let nextj = j + dirs[k][1];
            if(nexti>=0&&nexti<n&&nextj>=0&&nextj<m&&matrix[nexti][nextj]>matrix[i][j]){
                dp[i][j] = Math.max(dp[i][j],dfs(nexti,nextj)+1);
            }
        }
        return dp[i][j];
    }
    let res = 0;
    if(m==0||n==0){
        return 0;
    }
    for(let i=0;i<n;i++){
        for(let j=0;j<m;j++){
            res = Math.max(res,dfs(i,j));
        }
    }

    return res;

}
module.exports = {
    solve : solve
};