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.
---------------------------
暴解就可以了
class Solution { public int longestLine(int[][] M) { if (M.length == 0) return 0; int m = M.length, n = M[0].length; int len = 0; for (int i = 0; i < m; i++) { len = Math.max(len, check(M, i, 0, new int[]{0, 1})); } for (int i = 0; i < n; i++) { len = Math.max(len, check(M, 0, i, new int[]{1, 0})); } for (int i = 0; i < m; i++) { len = Math.max(len, check(M, i, 0, new int[]{1, 1})); len = Math.max(len, check(M, i, n - 1, new int[]{1, -1})); } for (int i = 1; i < n; i++) { len = Math.max(len, check(M, 0, i, new int[]{1, 1})); len = Math.max(len, check(M, 0, n - i - 1, new int[]{1, -1})); } return len; } private int check(int[][] matrix, int row, int col, int[] dir) { int len = 0, count = 0; for (; row >= 0 && col >= 0 && row < matrix.length && col < matrix[0].length; row += dir[0], col += dir[1]) { if (matrix[row][col] == 1) { count++; len = Math.max(len, count); }else { count = 0; } } return len; } }
No comments:
Post a Comment