使用深度优先遍历矩阵

Question

问题给定一个二维数组（矩阵），其高度和宽度可能不相等，仅包含 0 和 1。每个 0 代表土地，每个 1 代表河流的一部分。一条河流由任意数量的水平或垂直相邻（但不是对角线相邻）的 1 组成。形成河流的相邻 1 的数量决定了它的大小。编写一个函数，返回一个数组，该数组包含输入矩阵中表示的所有河流的大小。请注意，这些尺寸不需要按任何特定顺序排列。Input [[1,0,0,1,0],[1,0,1,0,0],[0,0,1,0,1],[1,0,1,0,1],[1,0,1,1,0],]Output [1,2,2,2,5]我的方法在评估了这个问题之后，我觉得这应该使用像算法这样的图形遍历来完成，也许是深度优先搜索。这正是我所做的。我从左上角遍历矩阵，看看是否访问了该值，如果未访问，如果值为 1，则我遍历它的所有节点并保留一个计数器以保持河流的大小。最后，我用总河流大小更新了一个数组列表。出于某种原因，我的结果不正确，我不确定我做错了什么。我也手动跟踪了我的代码，但无法找出问题所在。我的代码import java.util.ArrayList;class Program {  public static ArrayList<Integer> riverSizes(int[][] matrix) {    ArrayList<Integer> result = new ArrayList<Integer>();        boolean [][] visitStatus = new boolean [matrix.length][matrix[0].length];        for(int row = 0; row<matrix.length; row++){            for(int col = 0; col<matrix.length; col++){                int count = 0;                count = traverseMatrix(row,col,matrix,visitStatus,count);                result.add(count);            }        }        return result;  }    public static int traverseMatrix(int row, int col, int [][] matrix, boolean [][] visitStatus, int count){        if(visitStatus[row][col] == true){            return count;        }else if(matrix[row][col] == 0){            visitStatus[row][col] = true;            return count;        }else{            count++;            visitStatus[row][col] = true;            if(isValid(row,col-1,matrix)){                return traverseMatrix(row,col-1,matrix,visitStatus,count);            }            if(isValid(row,col+1,matrix)){                return traverseMatrix(row,col+1,matrix,visitStatus,count);            }            if(isValid(row-1,col,matrix)){                return traverseMatrix(row-1,col,matrix,visitStatus,count);            }            if(isValid(row+1,col,matrix)){                return traverseMatrix(row+1,col,matrix,visitStatus,count);            }        }        return count;    }

Answer 1

给定一个高度和宽度可能不相等的二维数组（矩阵） 

但是您正在对高度和宽度始终相同的矩阵进行操作

for(int row = 0; row<matrix.length; row++){ 
    for(int col = 0; col<matrix.length; col++){ .. }}

你应该像下面这样使用尺寸，我想剩下的就足够了..

  for(int row = 0; row<matrix.length; row++){ 
    for(int col = 0; col<matrix[row].length; col++){ .. }}

并且更改也需要应用到函数“isValid”中

public static boolean isValid(int row, int col,int[][] matrix){
    return (row >= 0 && row < matrix.length) && (col >= 0 && col < matrix[row].length);
}

Answer 2

转换count为局部变量并累加：

static int traverseMatrix(int row, int col, int[][] matrix, boolean[][] visitStatus) {

    if (visitStatus[row][col] || matrix[row][col] == 0) {

        return 0;

    }

    visitStatus[row][col] = true;

    int count = 1;

    if (isValid(row, col - 1, matrix)) {

        count += traverseMatrix(row, col - 1, matrix, visitStatus);

    }

    ...

    return count;

}

Answer 3

我的解决方案是用 C# 编写的，但它与 Java 类似：

您可以将 List 替换为 ArrayList

代码：

        public static List<int> RiverSizes(int[,] matrix)

        {

            var sizes = new List<int>();

            bool[,] visited = new bool[matrix.GetLength(0), matrix.GetLength(1)];

            for (int row = 0; row < matrix.GetLength(0); row++)

                for (int col = 0; col < matrix.GetLength(1); col++)

                    if (visited[row, col])

                        continue;

                    else

                        Traverse(matrix, row, col, visited, sizes);

           return sizes;

        }

        public static void Traverse(int[,] matrix, int row, int col, bool[,] visited, List<int> sizes)

        {

            int currentSize = 0;

            var toExplore = new List<int[]>

            {

                new int[] { row, col }

            };

            while (toExplore.Count > 0)

            {

                var current = toExplore[^1];

                toExplore.RemoveAt(toExplore.Count - 1);

                row = current[0];

                col = current[1];

                if (visited[row, col])

                    continue;

                visited[row, col] = true;

                if (matrix[row, col] == 0)

                    continue;

                currentSize++;

                foreach (int[] item in GetNeighbours(matrix, row, col, visited))

                    toExplore.Add(item);

            }

            if (currentSize > 0)

                sizes.Add(currentSize);

        }

        public static List<int[]> GetNeighbours(int[,] matrix, int row, int col, bool[,] visited)

        {

            List<int[]> neighbours = new List<int[]>();

            if (row > 0 && !visited[row - 1, col])

                neighbours.Add(new int[] { row - 1, col });

            if (row < matrix.GetLength(0) - 1 && !visited[row + 1, col])

                neighbours.Add(new int[] { row + 1, col });

            if (col > 0 && !visited[row, col - 1])

                neighbours.Add(new int[] { row, col - 1 });

            if (col < matrix.GetLength(1) - 1 && !visited[row, col + 1])

                neighbours.Add(new int[] { row, col + 1 });

            return neighbours;

        }

希望对您有帮助^-^