iterative version of easy recursive algorithm

Question

I have a quite simple question, I think. I've got this problem, which can be solved very easily with a recursive function, but which I wasn't able to solve iteratively.

Suppose you have any boolean matrix, like:

M:

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

I know this is not an ordinary boolean matrix, but it is useful for my example. You can note there is sort of zero-paths in there...

I want to make a function that receives this matrix and a point where a zero is stored and that transforms every zero in the same area into a 2 (suppose the matrix can store any integer even it is initially boolean)

(just like when you paint a zone in Paint or any image editor)

suppose I call the function with this matrix M and the coordinate of the upper right corner zero, the result would be:

111011111112
110111111122
001111111121
100111111121
110011111221
111111112211
111111122111
111112221111

well, my question is how to do this iteratively... hope I didn't mess it up too much

Thanks in advance!

Manuel

ps: I'd appreciate if you could show the function in C, S, python, or pseudo-code, please :D

Answer 1

There is a standard technique for converting particular types of recursive algorithms into iterative ones. It is called tail-recursion.

The recursive version of this code would look like (pseudo code - without bounds checking):

paint(cells, i, j) {
   if(cells[i][j] == 0) {
      cells[i][j] = 2;
      paint(cells, i+1, j);
      paint(cells, i-1, j);
      paint(cells, i, j+1);
      paint(cells, i, j-1);
   }
}

This is not simple tail recursive (more than one recursive call) so you have to add some sort of stack structure to handle the intermediate memory. One version would look like this (pseudo code, java-esque, again, no bounds checking):

paint(cells, i, j) {
    Stack todo = new Stack();
    todo.push((i,j))
    while(!todo.isEmpty()) {
       (r, c) = todo.pop();
       if(cells[r][c] == 0) {
          cells[r][c] = 2;
          todo.push((r+1, c));
          todo.push((r-1, c));
          todo.push((r, c+1));
          todo.push((r, c-1));              
       }          
    }
}

Answer 2

Pseudo-code:

Input: Startpoint (x,y), Array[w][h], Fillcolor f

Array[x][y] = f
bool hasChanged = false;
repeat
  for every Array[x][y] with value f:
    check if the surrounding pixels are 0, if so:
      Change them from 0 to f
      hasChanged = true
until (not hasChanged)