Recursively edit 2-D array using backtracking

Question

I have a 2-D array which contain 3 types of elements:

• C (Contaminant)
• R (Rock)
• W (Water)

The rule is that:

contaminant can seep through water but not through rocks.

---

Let's say I have the following input array:

WWWRW
CRRRR
RWWRW
WWWRR
WRRWC

So the cells which have 'C' as their value in the above array can contaminate in the same row and same column if water is present.

So the output would like something like this:

CCCRW
CRRRR
RWWRW
WWWRR
WRRCC

This is my naive attempt in 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;
}

This too is giving me wrong results.

---

This is the link which I am working on.

I know I have to solve this using via backtracking and recursion, but I am not able to come up with an apt algorithm to do so.

Any help will be hugely appreciated.

Answer 1

I won't explain the flood fill algorithm here, as you will find a lot of online tutorials on this subject.

Another way to solve the problem, is to repeatedly seep by one cell until no movement happens anymore. This is not very efficient but simple to understand.

The solution becomes more readable, if you extract some code into helper methods.

This helper method gets the neighbors of a cell by taking care to not exceed the borders. It uses a 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];
}

This method prints the array

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

The solution

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

Note that I don't take a contaminant to spread it around, but instead start with water and look if there is a contaminant around. This allows me to make at most one assignment per loop.

You could also create a copy at every (main) loop to get a realistic simulation in time. As the code is now, a contaminant might spread over several cells in a row in one loop.