The following algorithm would be my first attempt.
- Initialize a 2D array $A$ with given characters, 'C', 'W' or 'R'.
- 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.
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.