题解 | #矩阵最长递增路径# [P3]

从矩阵中的每一点开始一遍dfs, dfs时记录目前为止最长递增路径

对于current每个neighbor, 继续dfs的条件是:
 1. neighbor没有越界
 2. neighbor的值比current大

注意：这题dfs不需要记录visited, 因为能走的路径是单向的(因为condition2)
  i.e. A能走到B说明B>A, 那B之后必不可能revisit A

import java.util.*;

public class Solution {
    int[][] directions = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    int n, m, maxLen;

    public int solve (int[][] matrix) {
      n = matrix.length;
      m = matrix[0].length;
      maxLen = 0;
      
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
          solveRec(i, j, 0, matrix);
        }
      }
      return maxLen;
    }
  
    public void solveRec(int i, int j, int len, int[][] matrix) {
      if (++len > maxLen) 
        maxLen = len;
      
      for (int[] dir : directions) {
        int i_next = i + dir[0], j_next = j + dir[1];
        if (i_next < 0 || i_next >= n || j_next < 0 || j_next >= m)
          continue;
        if (matrix[i_next][j_next] <= matrix[i][j])
          continue;
        solveRec(i_next, j_next, len, matrix);
      }
    }
}