Java在多维数组中递归查找“stain”

Question

我正在尝试解决这个递归练习：

在一个多维棋盘中（M x N），每个元素都可以为空或为满。

“污点”大小是指相邻且值为'x'的元素数量。

例如，这是一个多维数组（数字是行/列号）

  | 0 | 1 | 2 | 3 | 4 |
0 |   | x |   |   | x |
1 | x |   |   | x | x |
2 |   |   | x | x |   |
3 | x |   |   |   |   |
4 | x | x | x |   |   |

有三个位置：

1. 行 (0,1)，(1,0) - 大小为2
2. 行 (0,4)，(1,3)，(1,4)，(2,2)，(2,3) - 大小为5
3. 行 (3,0)，(4,0)，(4,1)，(4,2) - 大小为4

我们需要编写一个递归函数，其签名为：

public static int stain (char [][] mat, int row, int col) 

该方法将获取一行和一列，并计算从该位置开始的污渍大小，如果没有污渍，则返回0。

我尝试编写该方法来解决它，但似乎我的做法有点混乱...你能指导我正确的方向吗？我不是在寻找直接的答案。

谢谢。

一些备注：

- 您可以更改数组以解决此问题。 - 您可以使用重载。 - 您不能使用任何循环。 - 您不能使用静态变量。

我的代码：

function stain (char[][] mat, int row, int col) 
{
    int col_len = mat.length;
    int row_len = mat[0].length;
    if (row < 0 || col < 0 || row >= row_len || col >= col_len)
        return 0;

    if (mat[row][col] != 'x')
        return 0;

    mat[row][col] = 'y';

    // Count current
    int count = 1;
    // Go Left
    count += stain (mat, row, col-1);
    // Go Right
    count += stain (mat, row, col+1);
    // Go Up
    count += stain (mat, row+1, col);
    // Go Down
    count += stain (mat, row-1, col);

    // Go UpperRight
    count += stain (mat, row+1, col+1);
    // Go UpperLeft
    count += stain (mat, row-1, col+1);

    // Go DownRight
    count += stain (mat, row+1, col-1);
    // Go DownLeft
    count += stain (mat, row-1, col-1);

    return count;
}

- D_R

---

它应该能工作，我只是相信可能有更好的解决方法。 - D_R

我有一种感觉，它不会正确地计算污渍的大小（我怀疑它会过度计数），也不会报告所有的污渍（它似乎没有记录每个污渍）。无论如何，有一个“工作代码”的代码审查交流。SO通常更适合于识别出不起作用的代码。 - user2864740

这可能更适合于codereview.stackexchange。 - Sinkingpoint

Answer 1

你不能使用循环

不幸的是，由于这种情况，你不会比现在更好。遍历所有邻居节点的递归代码可以简化为以下内容，尽管违反了限制的精神:

for (int dx = -1; dx <= 1; dx++) {
    for (int dy = -1; dy <= 1; dy++) {
        // This calls the function on the middle cell again. That's fine.
        count += stain(mat, row + dx, col + dy);
    }
}

由于不能使用循环，因此您确实需要使用稍微不同的参数明确地递归8次。这很容易出错且很麻烦，但没办法。

- user2357112