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

• 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;
}
``````

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