We don't need to memory which direction we searched.

We only need to search a direction if the previous value in this direction is 0.

Because if the previous value is 1, we have already searched on this cell and this direction when we loop through the previous cell.

For example:

The input matrix is:

[0,1,1]

We need to search on right for the location of (0, 1), because the location of (0, 0) is 0.

We do not need to search on right for the the location of (0, 2), because the location of (0, 1) is 1.

Below is my JAVA code:

class Solution {
public int longestLine(int[][] M) {
int result = 0;
for (int row = 0; row < M.length; row++) {
for (int col = 0; col < M[row].length; col++) {
if (M[row][col] == 0) {
continue;
}
if (col == 0 || M[row][col - 1] == 0) {
result = Math.max(result, findRight(M, row, col));
}
if (row == 0 || col == 0 || M[row - 1][col - 1] == 0) {
result = Math.max(result, findRightDown(M, row, col));
}
if (row == 0 || M[row - 1][col] == 0) {
result = Math.max(result, findDown(M, row, col));
}
if (row == 0 || col == M[row].length - 1 || M[row - 1][col + 1] == 0) {
result = Math.max(result, findLeftDown(M, row, col));
}
}
}
return result;
}
private static int findRight(int[][] M, int row, int col) {
return find(M, row, col, 0, 1);
}
private static int findRightDown(int[][] M, int row, int col) {
return find(M, row, col, 1, 1);
}
private static int findDown(int[][] M, int row, int col) {
return find(M, row, col, 1, 0);
}
private static int findLeftDown(int[][] M, int row, int col) {
return find(M, row, col, 1, -1);
}
private static int find(int[][] M, int row, int col, int rowDelta, int colDelta) {
int result = 0;
while (row >= 0 && row < M.length && col >= 0 &&
col < M[row].length && M[row][col] == 1) {
result++;
row += rowDelta;
col += colDelta;
}
return result;
}
}