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