C++, DP O(mn), with explanation


  • 0
    O

    From the start point (0,0), goes to (0,1), (0,2)..., (0,n-1), then check next row (1,0), (1,1), .. until (n-1,n-1).
    For each position (i,j), we calculate our consecutive state(i,j) based on current matrix[i][j] and the state of previous position state(previous). If matrix[i][j] is 0, the state is just nothing denoted as 0. or our consecutive state will be at least length 1. Then if the previous position has non-zero length, we can accumulate it to be state(current) = state(previous) + 1.

    The state(i, j) will be calculated from 0,0 to (m-1, n-1).

    • state[i][j] is 0 as default.
    • state[i][j] is at least 1 if matrix[i][j] is true
    • state[i][j] adds previous state if matrix[i][j] is true and previous state exists.

    There are four kind of states we will track.

    • h(horizontal) - to check left pixel, state[i][j-1]
    • v(vertical) | to check upper pixel, state[i-1][j]
    • d(diagonal) \ to check left-upper pixel, state[i-1][j-1],
    • a(anti-diagonal) / to check right-upper pixel, state[i-1][j+1]

    In the end, the maximal consecutive state will be the longest path we can get.

    struct Len{
        int h; // horizontal
        int v; // vertical
        int d; // dia
        int a; // anti-dia
        Len(): h(0), v(0), d(0), a(0) {}
    };
    int longestLine(vector<vector<int>>& M) {
        if(M.empty()){ return 0;}
        
        int m = (int)M.size(), n = (int)M[0].size();
        vector<vector<Len>> state;
        generate_n(back_inserter(state), m, [n]{ return vector<Len>(n);});
        
        int longest = 0;
        for(int i = 0; i != m; i++)
            for(int j = 0; j != n; j++) 
                if(M[i][j]) {
                    state[i][j].h = (j > 0)? state[i][j-1].h + 1: 1;
                    state[i][j].v = (i > 0)? state[i-1][j].v + 1: 1;
                    state[i][j].d = (i > 0 && j > 0)?       state[i-1][j-1].d + 1: 1;
                    state[i][j].a = (i > 0 && j + 1 < n)?   state[i-1][j+1].a + 1: 1;
                    longest = max(longest, max(state[i][j].h, max(state[i][j].v, max(state[i][j].d, state[i][j].a))));
                }
        return longest;
    }
    

Log in to reply
 

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