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

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

使用 Lee Algorithm 的改编很容易解决。

改编也叫洪水填充see this answer for a code example。

您基本上会使用堆栈或队列来保留受污染单元格的有效邻居。然后你会添加邻居的邻居，直到你到达一个停止点（没有更多的 W 单元与 C 单元相邻）。

Answer 2

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

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

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

此辅助方法通过注意不要超出边界来获取单元格的邻居。它使用 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);

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

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

Answer 3

由于这里的解决方案似乎是迭代的，我将提供另一种使用递归相对简单的解决方案。

算法

总之，该算法遍历二维数组中的所有 n 个元素，并在找到 "C" 后开始递归过程，将所有相邻的 "W" 元素转换为 "C"。如果没有相邻的 "W" 元素，它会终止递归并继续遍历数组。它基本上递归地填充数组中应该被污染的每个连接组件。

效率

该算法遍历每个元素，然后有效地实现深度优先搜索，当没有相邻元素可以被污染时终止。 DFS 的终止很重要，可以防止不必要的元素重复处理。该算法还具有内存效率，因为它就地修改了数组。

解决方案

public static void GenerateContaminant(string[,] arr)
{
    // Iterate through every element of the array and when you find a "C", 
    // propagate the contamination recursively to its neighbors.
    for (int row = 0; row < arr.GetLength(0); row++)
    {
        for (int col = 0; col < arr.GetLength(1); col++)
        {
            if (arr[row, col] == "C") {
                ContaminateRecurse(row, col, arr);
            }
        }
    }
    return;
}        

// Recurse from a "C" element and see if its neighbors should be contaminated.
public static void ContaminateRecurse(int row, int col, string[,] arr)
{
    arr[row, col] = "C";
    // Top Neighbor
    if (isValid(row-1, col, arr)) {
        ContaminateRecurse(row-1, col, arr);
    }
    // Bottom Neighbor
    if (isValid(row+1, col, arr)) {
        ContaminateRecurse(row+1, col, arr);
    }
    // Left Neighbor
    if (isValid(row, col-1, arr)) {
        ContaminateRecurse(row, col-1, arr);
    }
    // Right Neighbor
    if (isValid(row, col+1, arr)) {
        ContaminateRecurse(row, col+1, arr);
    }
    return;
}

// Makes sure that an element index is within the bounds of the array and is a 'W'.
public static bool isValid(int row, int col, string[,] arr) {
    if ((0 <= row && row < arr.GetLength(0)) && 
        (0 <= col && col < arr.GetLength(1)) && 
        arr[row,col] == "W") {
        return true;
    }
    else {
        return false;
    }
}

测试代码

这是我从您的 Rextester link 添加到完整测试程序代码的解决方案。我在开头复制了输入数组，因为我的算法修改了传递给它的数组。

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            // Set up input.
            string[,] arr = new string[,]
            {
                { "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" }
            };

            // Actual algorithm for solution. 
            // Make a copy for result since recursive solution will modify array in place.
            string[,] result = arr.Clone() as string[,];
            GenerateContaminant(result);

            printGrid("Input:", arr);
            printGrid("Output:", result);
        }


        public static void GenerateContaminant(string[,] arr)
        {
            // Iterate through every element of the array and when you find a "C", 
            // propagate the contamination recursively to its neighbors.
            for (int row = 0; row < arr.GetLength(0); row++)
            {
                for (int col = 0; col < arr.GetLength(1); col++)
                {
                    if (arr[row, col] == "C") {
                        ContaminateRecurse(row, col, arr);
                    }
                }
            }
            return;
        }        

        // Recurse from a "C" element and see if its neighbors should be contaminated.
        public static void ContaminateRecurse(int row, int col, string[,] arr)
        {
            arr[row, col] = "C";
            // Top Neighbor
            if (isValid(row-1, col, arr)) {
                ContaminateRecurse(row-1, col, arr);
            }
            // Bottom Neighbor
            if (isValid(row+1, col, arr)) {
                ContaminateRecurse(row+1, col, arr);
            }
            // Left Neighbor
            if (isValid(row, col-1, arr)) {
                ContaminateRecurse(row, col-1, arr);
            }
            // Right Neighbor
            if (isValid(row, col+1, arr)) {
                ContaminateRecurse(row, col+1, arr);
            }
            return;
        }

        // Makes sure that an element index is within the bounds of the array and is a 'W'.
        public static bool isValid(int row, int col, string[,] arr) {
            if ((0 <= row && row < arr.GetLength(0)) && 
                (0 <= col && col < arr.GetLength(1)) && 
                arr[row,col] == "W") {
                return true;
            }
            else {
                return false;
            }
        }

        // Write grid to console.
        public static void printGrid(string label, string[,] result) {
            Console.Write(label);
            Console.WriteLine();
            for (int rowValue = 0; rowValue < result.GetLength(0); rowValue++) {
                for (int colValue = 0; colValue < result.GetLength(1); colValue++) {
                    Console.Write(result[rowValue, colValue]);
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }

    }
}

结果：

Input:
WWWRW
CRRRR
RWWRW
WWWRR
WRRWC

Output:
CCCRW
CRRRR
RWWRW
WWWRR
WRRCC

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

Recursively edit 2-D array using backtracking

c#

arrays

algorithm

recursion

backtracking

算法

效率

解决方案

测试代码

结果：