Longest Increasing Sequence in a Matrix

题目地址：
http://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/

题目：

Given a n*n matrix where all numbers are distinct, find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1.

We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1.

Example:

Input:  mat[][] = {{1, 2, 9}
                   {5, 3, 8}
                   {4, 6, 7}}
Output: 4
The longest path is 6-7-8-9. 

解题思路：
这道题主要运用dfs+visited来做。时间复杂度是O(n^4)。

代码：

public class LongestIncreasingSequenceinaMatrix {

    /*    *       Input:  mat[][] = {    *               {1, 2, 9}                    {5, 3, 8}                    {4, 6, 7}}            Output: 4            The longest path is 6-7-8-9.    *    *    * */
    public static void main(String[] args){
        LongestIncreasingSequenceinaMatrix longestIncreasingSequenceinaMatrix = new LongestIncreasingSequenceinaMatrix();
        int[][] matrix = {{1, 2, 9},{5, 3, 8},{4, 6, 7}};
        List<Integer> rst = longestIncreasingSequenceinaMatrix.getPath(matrix);
        System.out.println(rst);
    }

    public List<Integer> getPath(int[][] matrix){
        List<Integer> rst = new ArrayList<>();
        if(matrix == null || matrix.length == 0){
            return rst;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        for(int i = 0; i <= matrix.length - 1; i++){
            for(int j = 0; j <= matrix[0].length - 1; j++){
                boolean[][] visited = new boolean[row][col];
                List<Integer> list = new ArrayList<>();
                // garantee that the next level should be valid                List<Integer> temp = dfs(matrix, visited, i, j, list, matrix[i][j] - 1);
                if(rst.size() < temp.size()){
                    rst = new ArrayList<>(temp);
                }
            }
        }
        return rst;
    }

    // the increasing sequence we are checking    private List<Integer> dfs(int[][] matrix, boolean[][] visited, int i, int j, List<Integer> list, int prev) {
        int row = matrix.length;
        int col = matrix[0].length;
        if(i < 0 || j < 0 || i >= row || j >= col || visited[i][j] || matrix[i][j] != prev + 1){
            return new ArrayList<>();
        }
        list.add(matrix[i][j]);
        visited[i][j] = true;
        // go top        List<Integer> top = dfs(matrix, visited, i - 1, j, new ArrayList<>(list), matrix[i][j]);
        if(list.size() < top.size()){
            list = new ArrayList<>(top);
        }
        // go bottom        List<Integer> bottom = dfs(matrix, visited, i + 1, j, new ArrayList<>(list), matrix[i][j]);
        if(list.size() < bottom.size()){
            list = new ArrayList<>(bottom);
        }
        //go left        List<Integer> left = dfs(matrix, visited, i, j - 1, new ArrayList<>(list), matrix[i][j]);
        if(list.size() < left.size()){
            list = new ArrayList<>(left);
        }
        // go right        List<Integer> right = dfs(matrix, visited, i, j + 1, new ArrayList<>(list), matrix[i][j]);
        if(list.size() < right.size()){
            list = new ArrayList<>(right);
        }
        visited[i][j] = false;
        return list;
    }

}

Follow up:
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

复杂度分析：

O(mn) time O(mn) space. DFS + DP

代码：

public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

public static void main(String[] args){
    LongestIncreasingSequenceinaMatrix longestIncreasingSequenceinaMatrix = new LongestIncreasingSequenceinaMatrix();
    int[][] matrix = {{9, 9, 4},{6, 6, 8},{2, 1, 1}};
    int rst = longestIncreasingSequenceinaMatrix.getPath(matrix);
    System.out.println(rst);
}

public int getPath(int[][] matrix) {
    List<Integer> rst = new ArrayList<>();
    if(matrix == null || matrix.length == 0){
        return 0;
    }
    int row = matrix.length;
    int col = matrix[0].length;
    for(int i = 0; i <= matrix.length - 1; i++){
        for(int j = 0; j <= matrix[0].length - 1; j++){
            boolean[][] visited = new boolean[row][col];
            // garantee that the next level should be valid            List<Integer> temp = dfs(matrix, visited, i, j,matrix[i][j] - 1);
            if(rst.size() < temp.size()){
                rst = new ArrayList<>(temp);
            }
        }
    }
    return rst.size();
}

private List<Integer> dfs(int[][] matrix, boolean[][] visited, int i, int j, int prev) {
    int row = matrix.length;
    int col = matrix[0].length;
    visited[i][j] = true;
    List<Integer> rst = new ArrayList<>();
    rst.add(matrix[i][j]);
    List<Integer> temp = new ArrayList<>();
    for(int[] dir : dirs){
        int x = i + dir[0];
        int y = j + dir[1];
        if(x < 0 || y < 0 || x >= row || y >= col || visited[x][y] || matrix[x][y] <= matrix[i][j]){
            continue;
        }
        List<Integer> curr = dfs(matrix, visited, x, y, matrix[i][j]);
        if(curr.size() > temp.size()){
            temp = curr;
        }
    }
    visited[i][j] = false;
    rst.addAll(temp);
    return rst;
}