使用深度优先遍历矩阵

Question

问题

给你一个二维数组（矩阵），其高度和宽度可能不相等，仅包含 0 和 1。每个0代表土地，每个1代表河流的一部分。一条河流由任意数量的水平或垂直相邻（但不是对角线相邻）的 1 组成。形成河流的相邻 1 的数量决定了它的大小。编写一个函数，该函数 returns 一个包含输入矩阵中表示的所有河流大小的数组。请注意，这些尺寸不需要按任何特定顺序排列。

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;
    }

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

Answer 1

将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 2

除了@OleksandrPyrohov 的回答之外，还要检查在调用 traverseMatrix 之前是否已经访问了当前单元格：

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++){
                if ( !visitStatus[row][col] ) {
                   int count = 0;
                   count = traverseMatrix(row,col,matrix,visitStatus,count);
                   result.add(count);
                }
            }
        }
        return result;
  }

Answer 3

you are given a two-dimensional array (matrix) of potentially unequal height and width

但是你对矩阵的高度和宽度总是相同的大小进行操作

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 4

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

您可以用 ArrayList 替换 List

代码：

        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;
        }

希望对你有帮助^-^

使用深度优先遍历矩阵

Use a depth first to traverse a matrix

java

algorithm

depth-first-search

data-structures