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.

Backtracking is useful if you have to search a path to a target, because then you can backtrack at dead-ends. But here, the contaminant is always only going one way and will always take all possible paths. Have a look at the [Flood fill algorithm](https://en.wikipedia.org/wiki/Flood_fill). — Olivier Jacot-Descombes, Feb 16 '19 at 17:00
@OlivierJacot-Descombes Sure I will have a look at that, can you suggest a way to rectify my naive implementation — Kunal Mukherjee, Feb 16 '19 at 17:16

Olivier Jacot-Descombes · Accepted Answer · 2019-02-28T13:37:14.447

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.

Yes it does, but as I wrote, it's up to you to create a copy if you want to preserve the original. — Olivier Jacot-Descombes, Feb 16 '19 at 18:26
So the `yield return` gives all the neighbors of a cell? Can you please explain this part `&& NeighboursOf(arr, i, j).Any(n => n == "C"))` ? — Kunal Mukherjee, Feb 16 '19 at 18:30
you have made good use of yield return and handled the boundary conditions well in the `neighborsOf` method, very clever — Kunal Mukherjee, Feb 16 '19 at 18:48
`yield return` is kind of magic. It returns one element of an enumeration but does not exit the method. What it does, is to return the 4 neighbors, if not at a border. If you prefer, you can also use the classic solution of returning a `List` instead. `.Any(n => n == 'C')` returns `true` if any of these neighbors is a contaminant. The condition is passed as [Lambda expression](https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/statements-expressions-operators/lambda-expressions). You could of course also loop through the neighbors in a for-loop instead. — Olivier Jacot-Descombes, Feb 16 '19 at 18:50

score 3 · Answer 2 · answered Feb 16 '19 at 20:36

Since the solutions here seem to be iterative, I'll provide another one that is relatively simple using recursion.

Algorithm

In summary, this algorithm iterates through all n elements in the 2D array and upon finding a "C", begins a recursive process of converting all adjacent "W" elements to "C". If there are no adjacent "W" elements, it terminates the recursion and continues onwards in its iteration through the array. It essentially recursively fills every connected component that should be contaminated in the array.

Efficiency

This algorithm iterates through every element, and then effectively implements a Depth-First search that terminates when no adjacent elements can be contaminated. The termination of the DFS is important and prevents unnecessary repeated processing of elements. This algorithm is also memory efficient since it modifies the array in place.

Solution

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

Test Code

Here is my solution added to the full tester code from your Rextester link. I copy the input array at the beginning since my algorithm modifies the array passed to it.

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

    }
}

Results:

Input:
WWWRW
CRRRR
RWWRW
WWWRR
WRRWC

Output:
CCCRW
CRRRR
RWWRW
WWWRR
WRRCC

score 0 · Answer 3 · answered Feb 16 '19 at 18:10

0

This is easy solvable using an adaptation of Lee Algorithm.

The adaptation is also called flood filling see this answer for a code example.

You would basically use a stack or queue for keeping the valid neighbors of a contaminated cell. Then you would add neighbors of neighbors until you reach a stop(there are no more W cells neighboring a C cell).

answered Feb 16 '19 at 18:10

Dan Butmalai

100
1
8

Is there an iterative solution possible? – Kunal Mukherjee Feb 16 '19 at 18:11
@KunalMukherjee the code example provided solves the problem using an iterative approach. – Dan Butmalai Feb 21 '19 at 20:56