[562. Longest Line of Consecutive One in Matrix] C++_2 methods: DFS and Dynamic Programming


  • 0

    The idea of these two methods are similar:
    For each position, try to find out the maximum length for each direction. Because we traverse our matrix from left to right, up to down, so we only need to consider 4 direction:
    for DFS:

    • left -> right;
    • up -> down;
    • upper-right -> lower-left;
    • upper-left -> lower-right;

    for DP, at M[i][j]:

    • [i-1][j]
    • [i][j-1]
    • [i-1][j-1]
    • [i-1][j+1]

    DP:

    class Solution {
    public:
    int longestLine(vector<vector<int>>& M) {
        if(M.empty()) return 0;
        int m = M.size();
        int n = M[0].size();
        int res = 0;
        vector<int> vec(4,0);
        vector<vector<vector<int> > > dp(m, vector<vector<int> >(n, vec));
        vector<pair<int, int> > d = {{0,-1},{-1,0},{-1,-1},{-1,1}};    
        
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(!M[i][j]) continue;
                dp[i][j] = {1,1,1,1};
                for(int k = 0; k < 4; ++k){
                    int ii = i + d[k].first;
                    int jj = j + d[k].second;
                    if(ii >= 0 && ii < m && jj >= 0 && jj < n){
                        dp[i][j][k] += dp[ii][jj][k];
                    }
                    res = max(dp[i][j][k], res);
                }
            }
        }
        return res;
    }
    };
    

    DFS, it seems that the running time is almost the same as DP method.

    class Solution {
    public:
    vector<pair<int, int> > d = {{0,1},{1,0},{1,1},{1,-1}};    
    // -, |, /, \ 
    // left -> right, up -> down, upper-right -> lower-left, upper-left -> lower-right
    int longestLine(vector<vector<int>>& M) {
        if(M.empty()) return 0;
        int m = M.size();
        int n = M[0].size();
        int res = 0;
        vector<int> vec(4, 0);
        vector<vector<vector<int> > > check(m, vector<vector<int> >(n, vec));
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(M[i][j] == 0) continue;
                for(int dir = 0; dir < 4; ++dir){
                    if(check[i][j][dir]) continue;
                    dfs(M, check, i, j, m, n, res, dir, 1);
                }
            }
        }
        return res;
    }
    
    int dfs(vector<vector<int>>& M, vector<vector<vector<int> > >& check, int i, int j, int m, int n, int& res, int k, int cur){// cur length at currnet direction
            int ii = i + d[k].first;
            int jj = j + d[k].second;
            if(ii >= 0 && ii < m && jj >= 0 && jj < n && M[ii][jj]){
                if(check[ii][jj][k] != 0){
                    check[i][j][k] = cur + check[ii][jj][k];
                }else{
                    check[i][j][k] = dfs(M, check, ii, jj, m, n, res, k, cur + 1);
                }
            }
            res = max(cur, max(res, check[i][j][k]));
            return cur;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.