class Solution {
    private int[][] dirs = new int[][] {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;

        int max = 0;

        Queue<int[]> q = new ArrayDeque<>();

        for (int r = 0; r < matrix.length; r++)
            for (int c = 0; c < matrix[0].length; c++) {
                if (next(r, c, matrix).size() == 0) q.add(new int[] {r, c, 1});
            }

        while (!q.isEmpty()) {
            int[] item = q.poll();
            max = Math.max(max, item[2]);
            for (int[] n: next(item[0], item[1], matrix)) q.add(new int[] { n[0], n[1], item[2]});
        }

        return max;
    }

    private List<int[][]> next(int r, int c, int[][] matrix) {
        ArrayList<int[][]> result = new ArrayList<>();

        for (int[] dir: dirs) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr == r && nc == c) continue;
            if (nr < 0 || nr >= matrix.length) continue;
            if (nc < 0 || nc >= matrix[0].length ) continue;
            if (matrix[nr][nc] <= matrix[r][c]) continue;

            result.add(new int[] { nr, nc });
        }

        return result;
    }
}