c# - 使用回溯递归编辑二维数组

Question

我有一个包含 3 种元素的二维数组:

• C(污染物)
• R(摇滚)
• W(水)

规则是:

contaminant can seep through water but not through rocks.

---

假设我有以下输入数组:

WWWRW
CRRRR
RWWRW
WWWRR
WRRWC

因此，如果存在水，则上述数组中具有 'C' 值的单元格可能会污染同一行和同一列。

所以输出会像这样:

CCCRW
CRRRR
RWWRW
WWWRR
WRRCC

这是我在 C# 中的幼稚尝试:

public static string[,] GenerateContaminant(int row, int column, string[,] arr)
{
    string[,] result = new string[row, column];
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            result[i, j] = arr[i, j];
        }
    }

    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < column; j++)
        {
            if (result[i, j] == "C")
            {
                for (int a = 0; a < row; a++)
                {
                    if (result[i, a] == "W")
                    {
                        result[i, a] = "C";
                    } 
                }

                for (int b = 0; b < column; b++)
                {
                    if (result[b, j] == "W")
                    {
                        result[b, j] = "C";
                    }
                }
            }
        }
    }

    return result;
}

这也给我错误的结果。

---

这是 link我正在研究它。

我知道我必须通过回溯和递归来解决这个问题，但我无法想出合适的算法来解决这个问题。

任何帮助将不胜感激。

Answer 1

我不会在这里解释洪水填充算法，因为你会发现很多关于这个主题的在线教程。

解决该问题的另一种方法是反复渗透一个单元格，直到不再发生移动为止。这不是很有效，但很容易理解。

如果您将一些代码提取到辅助方法中，解决方案将变得更具可读性。

此辅助方法通过注意不要超出边界来获取单元格的邻居。它使用 C# Iterator :

private static IEnumerable<char> NeighborsOf(char[,] env, int i, int j)
{
    if (i > 0) yield return env[i - 1, j];
    if (i < env.GetLength(0) - 1) yield return env[i + 1, j];
    if (j > 0) yield return env[i, j - 1];
    if (j < env.GetLength(1) - 1) yield return env[i, j + 1];
}

这个方法打印数组

private static void Print(char[,] env)
{
    Console.Clear();
    for (int i = 0; i < env.GetLength(0); i++) {
        for (int j = 0; j < env.GetLength(1); j++) {
            Console.Write(env[i, j]);
        }
        Console.WriteLine();
    }
    Thread.Sleep(1000);
}

解决方案

char[,] environment = {
    { 'W', 'W', 'W', 'R', 'W' },
    { 'C', 'R', 'R', 'R', 'R' },
    { 'R', 'W', 'W', 'R', 'W' },
    { 'W', 'W', 'W', 'R', 'R' },
    { 'W', 'R', 'R', 'W', 'C' }
};

var result = (char[,])environment.Clone(); // Creates a copy of the original.
bool didChange;
do {
    Print(result);
    didChange = false;
    for (int i = 0; i < result.GetLength(0); i++) {
        for (int j = 0; j < result.GetLength(1); j++) {
            if (result[i, j] == 'W' &&
                NeighborsOf(result, i, j).Any(n => n == 'C')) {
                result[i, j] = 'C';
                didChange = true;
            }
        }
    }
} while (didChange);

请注意，我不会将污染物四处散布，而是从水开始，看看周围是否有污染物。这允许我在每个循环中最多进行一次赋值。

您还可以在每个(主)循环中创建一个副本，以便及时获得逼真的模拟。按照现在的代码，污染物可能会在一个循环中连续分布在多个单元格上。