0
$\begingroup$

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

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.

$\endgroup$
1
$\begingroup$

The following algorithm would be my first attempt.

  1. Initialize a 2D array $A$ with given characters, 'C', 'W' or 'R'.
  2. Loop $m+n-2$ times.
    • In each loop, iterate over all cells of $A$. For each cell, check whether it is 'C'. If yes, change all of it neighbors that are 'W' to 'C'. Otherwise, do nothing.

Here is an illustration of the step 2 on the example given in the question, where after 3 loops the situation will not change any more although we have specified 5+5-2=8 loops. Looping $m+n-2$ times guarantees that all contaminated elements will be found although the situation should become stable earlier in general. (In fact, the number of times needed is the longest Manhattan distance from a water cell that will be contaminated to the nearest cell that is contaminated initially.) $m+n-2$ is chosen here just for its simplicity.

WWWRW     CWWRW     CCWRW     CCCRW              CCCRW
CRRRR     CRRRR     CRRRR     CRRRR              CRRRR
RWWRW ->  RWWRW  -> RWWRW  -> RWWRW  -> (stable) RWWRW
WWWRR     WWWRR     WWWRR     WWWRR              WWWRR
WRRWC     WRRCC     WRRCC     WRRCC              WRRCC

Once the above simple and sound algorithm has been working well, we can consider a couple of improvements.

  • Once we have checked a cell with value 'C', we will mark it as 'V' after we have changed its neighbors. In each loop, we will ignore cells with value 'V'.
  • We can use a queue to list the cells to be checked. Cells that are changed to 'C' will be appended to the queue. Once the queue is empty, the algorithm stops.

I know I have to solve this using via backtracking and recursion.

Not necessarily.

The technique used in the above algorithm is looping simply. Or nested loops to advance the frontier of contaminants. You can imagine the contaminants are spreading to their immediate neighbors uniformly by one tick of time. Ticks of time correspond to the outer loop while all contaminant correspond to the inner loop.

$\endgroup$
  • $\begingroup$ may I know why loop over n - 2 times? $\endgroup$ – Kunal Mukherjee Feb 16 at 15:15
  • 1
    $\begingroup$ $m+n-2$ times, where $m$ and $n$ are the sizes of the rectangle. The distance from top-left corner to the bottom-right corner is $m+n-2$. For each tick of time, the contaminant expands by one edge. $\endgroup$ – Apass.Jack Feb 16 at 15:25
  • $\begingroup$ can you provide a visualization? I am having a tough time to visualize the distance of top left to bottom right corner which you're talking about. Also as per my understanding its 2 loops, for (i <- 0 to m) for (j <- 0 to n - 2) right? $\endgroup$ – Kunal Mukherjee Feb 16 at 15:28
  • $\begingroup$ $m+n-2$ is my (stupid) upper bound. The contamination may become stable and hence can finish much earlier. In the example, only 3 rounds of inner loops is needed. The inner loop is `for (int i = 0; i < m; i++) for (int j= 0; j < n; j++) { /* check if A[i][j] is C and spread C if yes */ }. Note that the inner loop is a nested loop by itself. Note that I am talking about the simple naive algorithm here. $\endgroup$ – Apass.Jack Feb 17 at 5:01
  • 1
    $\begingroup$ Please check the graphic illustration in the updated answer. $\endgroup$ – Apass.Jack Feb 17 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.