'''
If the grid[i][j] == 1, then:
horizontal: dp[i][j] = dp[i][j-1] + 1
vertical: dp[i][j] = dp[i-1][j] + 1
diag: dp[i][j] = dp[i-1][j-1] + 1
anti-diag: dp[i][j] = dp[i-1][j+1] + 1
'''
class Solution:
def longestLine(self, mat: List[List[int]]) -> int:
rows = len(mat)
cols = len(mat[0])
dp = [[[0] * 4 for i in range(cols)] for j in range(rows)]
res = 0
for i in range(rows):
for j in range(cols):
if mat[i][j] == 1:
# horizontal: dp[i][j] = dp[i][j-1] + 1
dp[i][j][0] = dp[i][j-1][0] + 1 if j > 0 else 1
# vertical: dp[i][j] = dp[i-1][j] + 1
dp[i][j][1] = dp[i-1][j][1] + 1 if i > 0 else 1
# diag: dp[i][j] = dp[i-1][j-1] + 1
dp[i][j][2] = dp[i-1][j-1][2] + 1 if i > 0 and j > 0 else 1
# anti-diag: dp[i][j] = dp[i-1][j+1] + 1
dp[i][j][3] = dp[i-1][j+1][3] + 1 if i > 0 and j < cols-1 else 1
max_dp = max(dp[i][j])
res = max(res, max_dp)
return res
# class Solution:
# def longestLine(self, M: List[List[int]]) -> int:
# if not M:
# return 0
# R = len(M)
# C =…
