DFS straightforward


  • 1
    L

    not optimal solution, but accepted.

        int maxLen=0;
        public int longestLine(int[][] M) {
            if(M==null||M.length==0||M[0].length==0) return 0;
            int A=M.length;int B=M[0].length;
            for(int i=0;i<A;i++)
            for(int j=0;j<B;j++){
                if(M[i][j]==1){
                    dfs(M,i,j,0);
                    dfs(M,i,j,1);
                    dfs(M,i,j,2);
                    dfs(M,i,j,3);
                }
            }
            return maxLen;
        }
        
        int [][]dir={{1,0},{0,1},{-1,-1},{-1,1}};
        
        private void dfs(int[][] M,int i,int j,int mode){
            
            int len=0;int A=M.length;int B=M[0].length;
            int x=i,y=j;
            while(x>=0&&x<A&&y>=0&&y<B&&M[x][y]==1){
                x=x+dir[mode][0];
                y=y+dir[mode][1];
                len++;
            }
            maxLen=Math.max(maxLen,len);
            
        }
    

  • 0
    P

    @leon1223 why you have only 4 dirs? why dirs do not have {-1, 0}, {0, -1}, {1, -1}, {1, 1}?


  • 0
    L

    just seach one side. If two directions, we can add visited[], to avoid repeated search; will be more optimal.


Log in to reply
 

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