## 题目描述：

LeetCode 562. Longest Line of Consecutive One in Matrix

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example:

```Input:
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]
Output: 3
```

Hint: The number of elements in the given matrix will not exceed 10,000.

## 解题思路：

```h[x][y] = M[x][y] * (h[x - 1][y]  + 1)

v[x][y] = M[x][y] * (v[x][y - 1]  + 1)

d[x][y] = M[x][y] * (d[x - 1][y - 1]  + 1)

a[x][y] = M[x][y] * (a[x + 1][y - 1]  + 1)```

## Python代码：

``````class Solution(object):
def longestLine(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
h, w = len(M), len(M) and len(M[0]) or 0
ans = 0

#horizontal & diagonal
diag = [[0] * w for r in range(h)]
for x in range(h):
cnt = 0
for y in range(w):
cnt = M[x][y] * (cnt + 1)
diag[x][y] = M[x][y]
if x > 0 and y > 0 and M[x][y] and diag[x - 1][y - 1]:
diag[x][y] += diag[x - 1][y - 1]
ans = max(ans, cnt, diag[x][y])

#vertical & anti-diagonal
adiag = [[0] * w for r in range(h)]
for x in range(w):
cnt = 0
for y in range(h):
cnt = M[y][x] * (cnt + 1)
if y < h - 1 and x > 0 and M[y][x] and adiag[y + 1][x - 1]:

return ans
``````

Pingbacks已关闭。