connected sum | shawnlincoding

connected sum | shawnlincoding
题目是给定一个矩阵，里面有0和非0值. 求最大的连通的非0元素的加和。用dfs做吧，要记得update访问过的元素为0follow up是如果有负数在里面怎么办。

    public int connectedSum(int[][] matrix){

        if(matrix == null || matrix.length == 0){

            return 0;

        }

        int m = matrix.length, n = matrix[0].length;

        boolean[][] marked = new boolean[m][n];

        int max = 0;

        for(int i = 0; i < m; i++){

            for(int j = 0; j < n; j++){

                if(!marked[i][j] && matrix[i][j] != 0){

                    max = Math.max(max, dfs(matrix, i, j, marked));

                }

            }

        }

        return max;

    }

     

    private int dfs(int[][] matrix, int i, int j, boolean[][] marked){

        if(!isValidIdx(matrix, i, j)){

            return 0;

        }

        if(marked[i][j]){

            return 0;

        }

        if(matrix[i][j] == 0){

            return 0;

        }else{

            marked[i][j] = true;

            return matrix[i][j] + dfs(matrix, i + 1, j, marked) +

                dfs(matrix, i - 1, j, marked) +

                dfs(matrix, i, j + 1, marked) +

                dfs(matrix, i, j - 1, marked);

        }

    }

     

    private boolean isValidIdx(int[][] matrix, int i, int j){

        int m = matrix.length, n = matrix[0].length;

        return i >= 0 && i < m && j >= 0 && j < n;

    }

Read full article from connected sum | shawnlincoding