Wednesday, January 20, 2016

LeetCode [329] Longest Increasing Path in a Matrix

329. Longest Increasing Path in a Matrix
Hard
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:
Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    vector<vector<int>> dir{{1,0},{-1,0},{0,-1},{0,1}};
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m==0) return 0;
        int n = matrix[0].size();
        if(n==0) return 0;
        
        vector<vector<int>> dp(m, vector<int>(n, -1));
        int ret = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(dp[i][j]<0){
                    dfs(matrix, dp, i, j, m, n);
                }
                ret = max(ret, dp[i][j]);
            }
        }
        return ret;
    }
    
    void dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int i, int j, int m, int n){
        dp[i][j] = 1;
        for(auto d:dir){
            int ii = i+d[0], jj = j+d[1];
            if(ii>=0 && ii<m && jj>=0 && jj<n && matrix[i][j]<matrix[ii][jj]){
                if(dp[ii][jj]<0){
                    dfs(matrix, dp, ii, jj, m, n);
                }
                dp[i][j] = max(dp[i][j], 1+dp[ii][jj]);
            }
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//Java
class Solution {
    int[][] dir = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
    int ret = 0;
    int m, n;
    int[][] dp;
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        if(m==0) return 0;
        n = matrix[0].length;
        if(n==0) return 0;
        
        dp = new int[m][n];
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                dp[i][j] = -1;
            }
        }

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(dp[i][j]<0) helper(matrix, i, j);
                ret = Math.max(ret, dp[i][j]);
            }
        }
        
        return ret;
    }

    void helper(int[][] matrix, int i, int j){
        dp[i][j] = 1;
        for(int[] d : dir){
            int ii = i + d[0];
            int jj = j + d[1];
            if(ii>=0 && ii<m && jj>=0 && jj<n && matrix[i][j]<matrix[ii][jj]){
                if(dp[ii][jj]<0){
                    helper(matrix, ii, jj);
                }
                dp[i][j] = Math.max(dp[i][j], dp[ii][jj]+1);
            }
        }
    }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//O((mn)^2)
class Solution {
    int m, n;
    int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        if(m == 0) return 0;
        n = matrix[0].length;
        if(n == 0) return 0;

        int[][] dp = new int[m][n];
        for(int i=0; i<m; ++i){
            Arrays.fill(dp[i], 1);
        }

        boolean cont = true;
        while(cont){
            cont = false;
            for(int i=0; i<m; ++i){
                for(int j=0; j<n; ++j){
                    for(int[] d : dirs){
                        int ii = i+d[0], jj = j+d[1];
                        if(ii>=0 && ii<m && jj>=0 && jj<n){
                            if(matrix[ii][jj]>matrix[i][j]){
                                if(dp[ii][jj]<dp[i][j]+1){
                                    cont = true;
                                    dp[ii][jj] = dp[i][j]+1;
                                }
                            }
                        }
                    }
                }
            }
        }

        int ret = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                ret = Math.max(ret, dp[i][j]);
            }
        }

        return ret;
    }
}
Posted by at
Labels: , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)