首先使用深度遍历矩阵

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

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

除了@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 4

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

您可以将列表替换为数组列表

法典：

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

我希望它对^-^有所帮助