/*
the DFS here is basically like DP with memorization. Every cell that has been computed will not be computed again,
only a value look-up is performed. So this is O(mn), m and n being the width and height of the matrix.
To be exact, each cell can be accessed 5 times at most: 4 times from the top, bottom, left and right and one time
from the outermost double for loop. 4 of these 5 visits will be look-ups except for the first one.
So the running time should be lowercase o(5mn), which is of course O(mn).


To get max length of increasing sequences:

1. Do DFS from every cell
2. Compare every 4 direction and skip cells that are out of boundary or smaller
3. Get matrix max from every cell's max (because each cell will have lengths from four directions)
4. Use matrix[x][y] <= matrix[i][j] so we don't need a visited[m][n] array
5. The key is to cache the distance because it's highly possible to revisit a cell

*/
public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        int[][] cache = new int[m][n];
        int max = 0;
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                int len = dfs(matrix, i, j, cache, dirs);
                max = Math.max(max, len);
            }
        }
        return max;
    }

    public int dfs(int[][] matrix, int i, int j, int[][] cache, int[][] dirs) {
        if(cache[i][j] != 0) return cache[i][j];
        int max = 1;
        for(int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if(x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= matrix[i][j]) continue;
            int len = 1 + dfs(matrix, x, y, cache, dirs);
            max = Math.max(max, len);
        }
        cache[i][j] = max;
        return max;
    }
}