使用深度优先遍历矩阵

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

给定一个高度和宽度可能不相等的二维数组（矩阵）&nbsp;但是您正在对高度和宽度始终相同的矩阵进行操作for(int&nbsp;row&nbsp;=&nbsp;0;&nbsp;row<matrix.length;&nbsp;row++){&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;col&nbsp;=&nbsp;0;&nbsp;col<matrix.length;&nbsp;col++){&nbsp;..&nbsp;}}你应该像下面这样使用尺寸，我想剩下的就足够了..&nbsp;&nbsp;for(int&nbsp;row&nbsp;=&nbsp;0;&nbsp;row<matrix.length;&nbsp;row++){&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;col&nbsp;=&nbsp;0;&nbsp;col<matrix[row].length;&nbsp;col++){&nbsp;..&nbsp;}}并且更改也需要应用到函数“isValid”中public&nbsp;static&nbsp;boolean&nbsp;isValid(int&nbsp;row,&nbsp;int&nbsp;col,int[][]&nbsp;matrix){ &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(row&nbsp;>=&nbsp;0&nbsp;&&&nbsp;row&nbsp;<&nbsp;matrix.length)&nbsp;&&&nbsp;(col&nbsp;>=&nbsp;0&nbsp;&&&nbsp;col&nbsp;<&nbsp;matrix[row].length); }

Answer 2

转换count为局部变量并累加：static int traverseMatrix(int row, int col, int[][] matrix, boolean[][] visitStatus) {&nbsp; &nbsp; if (visitStatus[row][col] || matrix[row][col] == 0) {&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; }&nbsp; &nbsp; visitStatus[row][col] = true;&nbsp; &nbsp; int count = 1;&nbsp; &nbsp; if (isValid(row, col - 1, matrix)) {&nbsp; &nbsp; &nbsp; &nbsp; count += traverseMatrix(row, col - 1, matrix, visitStatus);&nbsp; &nbsp; }&nbsp; &nbsp; ...&nbsp; &nbsp; return count;}

Answer 3

我的解决方案是用 C# 编写的，但它与 Java 类似：您可以将 List 替换为 ArrayList代码：&nbsp; &nbsp; &nbsp; &nbsp; public static List<int> RiverSizes(int[,] matrix)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var sizes = new List<int>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bool[,] visited = new bool[matrix.GetLength(0), matrix.GetLength(1)];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int row = 0; row < matrix.GetLength(0); row++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int col = 0; col < matrix.GetLength(1); col++)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (visited[row, col])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Traverse(matrix, row, col, visited, sizes);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return sizes;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public static void Traverse(int[,] matrix, int row, int col, bool[,] visited, List<int> sizes)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int currentSize = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var toExplore = new List<int[]>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new int[] { row, col }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; };&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (toExplore.Count > 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var current = toExplore[^1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; toExplore.RemoveAt(toExplore.Count - 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; row = current[0];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; col = current[1];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (visited[row, col])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; visited[row, col] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (matrix[row, col] == 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; continue;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currentSize++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; foreach (int[] item in GetNeighbours(matrix, row, col, visited))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; toExplore.Add(item);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (currentSize > 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sizes.Add(currentSize);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public static List<int[]> GetNeighbours(int[,] matrix, int row, int col, bool[,] visited)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; List<int[]> neighbours = new List<int[]>();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (row > 0 && !visited[row - 1, col])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; neighbours.Add(new int[] { row - 1, col });&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (row < matrix.GetLength(0) - 1 && !visited[row + 1, col])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; neighbours.Add(new int[] { row + 1, col });&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (col > 0 && !visited[row, col - 1])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; neighbours.Add(new int[] { row, col - 1 });&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (col < matrix.GetLength(1) - 1 && !visited[row, col + 1])&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; neighbours.Add(new int[] { row, col + 1 });&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return neighbours;&nbsp; &nbsp; &nbsp; &nbsp; }希望对您有帮助^-^