Java Easy-to-understand Solution


  • 0
    public class Solution {
        
        int[][] dirs = { {0,1}, {1,0}, {0,-1}, {-1,0}, {-1,1}, {-1,-1}, {1,-1}, {1,1} };
        
        int[][] explored; // 1000->horizontal, 0100->vertical, 0010->diagonal, 0001->antidiagonal
    
        private int traval(int[][] M, int[] dir, int i, int j, int marker) {
            int length = 0;
            do {
                length++;
                explored[i][j] |= marker;
                i += dir[0];
                j += dir[1];
            } while(i>=0 && i<M.length && j>=0 && j<M[0].length && M[i][j]==1);
            return length;
        }
        
        public int longestLine(int[][] M) {
            if(M.length==0)
                return 0;
            explored = new int[M.length][M[0].length];
            int longest = 0;
            for(int i=0; i<M.length; i++) {
                for(int j=0; j<M[0].length; j++) {
                    if(M[i][j]==1 && explored[i][j]!=15) {
                        for(int[] dir : dirs) {
                            if(dir[1]==0 && (explored[i][j]&8)==0)
                                longest = Math.max(longest, traval(M,dir,i,j,8));
                            else if(dir[0]==0 && (explored[i][j]&4)==0)
                                longest = Math.max(longest, traval(M,dir,i,j,4));
                            else if(dir[0]==dir[1] && (explored[i][j]&2)==0)
                                longest = Math.max(longest, traval(M,dir,i,j,2));
                            else if(dir[0]==-dir[1] && (explored[i][j]&1)==0)
                                longest = Math.max(longest, traval(M,dir,i,j,1));
                        }
                    }
                }
            }
            return longest;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.