http://bookshadow.com/weblog/2017/04/23/leetcode-longest-line-of-consecutive-one-in-matrix/
https://segmentfault.com/a/1190000017237619
https://discuss.leetcode.com/topic/87197/java-o-nm-time-dp-solution
https://discuss.leetcode.com/topic/87389/simple-and-concise-java-solution-easy-to-understand-o-m-n-space
https://www.jianshu.com/p/60d9c17617b8
递归的解法，同时maintain一个最大值，注意8个方向中只需要走4个方向即可。
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:
Hint: The number of elements in the given matrix will not exceed 10,000.
给定01矩阵M，计算矩阵中一条线上连续1的最大长度。一条线可以为横向、纵向、主对角线、反对角线。
提示：给定矩阵元素个数不超过10,000
X.https://segmentfault.com/a/1190000017237619
public int longestLine(int[][] M) {
if (M == null || M.length == 0 || M[0].length == 0) return 0;
int max = 0, m = M.length, n = M[0].length;
int[] row = new int[m];
int[] col = new int[n];
int[] d = new int[m+n];
int[] ad = new int[m+n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
row[i]++;
col[j]++;
d[i+j]++;
ad[j-i+m]++;
max = Math.max(max, Math.max(row[i], col[j]));
max = Math.max(max, Math.max(d[i+j], ad[j-i+m]));
} else {
row[i] = 0;
col[j] = 0;
d[i+j] = 0;
ad[j-i+m] = 0;
}
}
}
return max;
}
如果上面的解法的坐标转换不好想的话，我们也可以考虑用DP解法来做，我们建立一个三维dp数组，其中dp[i][j][k]表示从开头遍历到数字nums[i][j]为止，第k种情况的连续1的个数，k的值为0，1，2，3，分别对应水平，竖直，对角线和逆对角线这四种情况。之后就是更新dp数组的过程了，如果如果数字为0的情况直接跳过，然后水平方向就加上前一个的dp值，竖直方向加上上面一个数字的dp值，对角线方向就加上右上方数字的dp值，逆对角线就加上左上方数字的dp值，然后每个值都用来更新结果res
https://www.jianshu.com/p/6bdf7b29b752
dp[i][j][k]表示从开头遍历到数字nums[i][j]为止，第k种情况的连续1的个数.
k的值为0，1，2，3，分别对应水平，竖直，对角线和逆对角线这四种情况。
更新dp数组过程:
如果如果数字为0的情况直接跳过，然后水平方向就加上前一个的dp值，竖直方向加上上面一个数字的dp值，对角线方向就加上右上方数字的dp值，逆对角线就加上左上方数字的dp值，然后每个值都用来更新结果res.
k的值为0，1，2，3，分别对应水平，竖直，对角线和逆对角线这四种情况。
更新dp数组过程:
如果如果数字为0的情况直接跳过，然后水平方向就加上前一个的dp值，竖直方向加上上面一个数字的dp值，对角线方向就加上右上方数字的dp值，逆对角线就加上左上方数字的dp值，然后每个值都用来更新结果res.
public int longestLine(int[][] M) {
int n = M.length, max = 0;
if (n == 0) return max;
int m = M[0].length;
int[][][] dp = new int[n][m][4];
for (int i=0;i<n;i++)
for (int j=0;j<m;j++) {
if (M[i][j] == 0) continue;
for (int k=0;k<4;k++) dp[i][j][k] = 1;
if (j > 0 && M[i][j-1] == 1) dp[i][j][0] += dp[i][j-1][0]; // horizontal line
if (j > 0 && i > 0 && M[i-1][j-1] == 1) dp[i][j][1] += dp[i-1][j-1][1]; // diagonal line
if (i > 0 && M[i-1][j] == 1) dp[i][j][2] += dp[i-1][j][2]; // vertical line
if (j < m-1 && i > 0 && M[i-1][j+1] == 1) dp[i][j][3] += dp[i-1][j+1][3]; // anti-diagonal line
max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
max = Math.max(max, Math.max(dp[i][j][2], dp[i][j][3]));
}
return max;
动态规划（Dynamic Programming）
分表用二维数组h[x][y], v[x][y], d[x][y], a[x][y]表示以元素M[x][y]结尾，横向、纵向、主对角线、反对角线连续1的最大长度
状态转移方程如下：
https://discuss.leetcode.com/topic/87204/verbose-java-solution-hashset-only-search-later-cells
For each
unvisited direction of each 1, we search length of adjacent 1s and mark those 1s as visited in that direction. And we only need to search 4 directions: right, down, down-right, down-left. We only access each cell at max 4 times, so time complexity is O(mn). m = number of rows, n = number of columns. public int longestLine(int[][] M) {
int m = M.length;
if (m <= 0) return 0;
int n = M[0].length;
if (n <= 0) return 0;
int max = 0;
int[][] dirs = {{0, 1}, {1, 0}, {1, 1}, {1, -1}};
List<Set<String>> memo = new ArrayList<>();
for (int i = 0; i < 4; i++) {
memo.add(new HashSet<String>());
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 0) continue;
String pos = i + "," + j;
for (int k = 0; k < 4; k++) {
if (!memo.get(k).contains(pos)) {
int count = 0;
for (int r = i, c = j; r < m && r >= 0 && c < n && c >= 0; r += dirs[k][0], c += dirs[k][1]) {
if (M[r][c] == 1) {
count++;
memo.get(k).add(r + "," + c);
}
else break;
}
max = Math.max(max, count);
}
}
}
}
return max;
}public int longestLine(int[][] M) {
if (M.length == 0 || M[0].length == 0) {
return 0;
}
int max = 0;
int[] col = new int[M[0].length];
int[] diag = new int[M.length + M[0].length];
int[] antiD = new int[M.length + M[0].length];
for (int i = 0; i < M.length; i++) {
int row = 0;
for (int j = 0; j < M[0].length; j++) {
if (M[i][j] == 1) {
row++;
col[j]++;
diag[j + i]++;
antiD[j - i + M.length]++;
max = Math.max(max, row);
max = Math.max(max, col[j]);
max = Math.max(max, diag[j + i]);
max = Math.max(max, antiD[j - i + M.length]);
} else {
row = 0;
col[j] = 0;
diag[j + i] = 0;
antiD[j - i + M.length] = 0;
}
}
}
return max;https://www.jianshu.com/p/60d9c17617b8
第一种方法是直接做搜索，LC现在感觉大数据的test case少了，所以繁琐一点也是能过的.
对于每一个点，朝8个方向进行搜索 （其实朝前向的四个方向就可以） 同时将扫过的点记录下来，以便不往回找.
https://blog.csdn.net/katrina95/article/details/79311355对于每一个点，朝8个方向进行搜索 （其实朝前向的四个方向就可以） 同时将扫过的点记录下来，以便不往回找.
递归的解法，同时maintain一个最大值，注意8个方向中只需要走4个方向即可。
下面我们来优化空间复杂度，用一种类似于DFS的思路来解决问题，我们在遍历到为1的点时，对其水平方向，竖直方向，对角线方向和逆对角线方向分别不停遍历，直到越界或者遇到为0的数字，同时用计数器来累计1的个数，这样就可以用来更新结果res了，就不用把每个中间结果都保存下来
int longestLine(vector<vector<int>>& M) { if (M.empty() || M[0].empty()) return 0; int m = M.size(), n = M[0].size(), res = 0; vector<vector<int>> dirs{{1,0},{0,1},{-1,-1},{-1,1}}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (M[i][j] == 0) continue; for (int k = 0; k < 4; ++k) { int cnt = 0, x = i, y = j; while (x >= 0 && x < m && y >= 0 && y < n && M[x][y] == 1) { x += dirs[k][0]; y += dirs[k][1]; ++cnt; } res = max(res, cnt); } } } return res; }https://discuss.leetcode.com/topic/87228/java-strightforward-solution
public int longestLine(int[][] M) {
if(M == null) return 0;
int res = 0;
for(int i =0;i<M.length;i++){
for(int j = 0;j<M[0].length;j++){
if(M[i][j] == 1){
res = Math.max(res,getMaxOneLine(M, i, j));
}
}
}
return res;
}
final int [][] dirs = new int[][]{{1,0},{0,1},{1,1},{1,-1}};
private int getMaxOneLine(int [][] M, int x, int y){
int res = 1;
for(int [] dir:dirs){
int i = x+dir[0];
int j = y+dir[1];
int count = 1;
while(isValidPosition(M, i, j) && M[i][j] == 1){
i+=dir[0];
j+=dir[1];
count++;
}
res = Math.max(count,res);
}
return res;
}
private boolean isValidPosition(int M[][], int i, int j){
return (i<M.length && j<M[0].length && i>=0 && j>=0);
}
lc solution：用三维数组压缩代码
public int longestLine(int[][] M) {
int rows = M.length;
if (rows == 0) return 0;
int cols = M[0].length;
int res = 0;
// 0 horizaental, 1 vertical, 2 diagonal, 3 anti-diagonal
int[][][] dp = new int[rows][cols][4];
for (int i = 0 ; i < rows ; i++) {
for (int j = 0 ; j < cols ; j++) {
if (M[i][j] == 1) {
dp[i][j][0] = j > 0 ? dp[i][j-1][0] + 1 : 1;
dp[i][j][1] = i > 0 ? dp[i-1][j][1] + 1 : 1;
dp[i][j][2] = (i > 0 && j > 0) ? dp[i-1][j-1][2] + 1 : 1;
dp[i][j][3] = (i > 0 && j < cols - 1) ? dp[i-1][j+1][3] + 1 : 1;
res = Math.max(dp[i][j][0], res);
res = Math.max(dp[i][j][1], res);
res = Math.max(dp[i][j][2], res);
res = Math.max(dp[i][j][3], res);
}
}
}
return res;
}
