简易递归算法的迭代版本

Question

我想我有一个很简单的问题。我有这个问题，可以用递归函数很容易地解决，但我不能迭代地解决。

假设你有任何布尔矩阵，比如：

M：

111011111110
110111111100
001111111101
100111111101
110011111001
111111110011
111111100111
111110001111

我知道这不是一个普通的布尔矩阵，但它对我的示例很有用。你可以注意到那里有一种零路径...

我想做一个函数来接收这个矩阵和一个存储零的点，并将同一区域中的每个零转换为2(假设矩阵可以存储任何整数，即使它最初是布尔值)

(就像在paint或任何图像编辑器中绘制区域时一样)

假设我用这个矩阵M和右上角零的坐标调用函数，结果将是：

111011111112
110111111122
001111111121
100111111121
110011111221
111111112211
111111122111
111112221111

嗯，我的问题是如何迭代地做到这一点……希望我没有搞砸太多

提前感谢！

曼纽尔

ps:如果您能用C、S、python或伪代码显示函数，我将不胜感激

Answer 1

有一种将特定类型的递归算法转换为迭代算法的标准技术。它被称为tail-recursion。

此代码的递归版本将如下所示(伪代码-无边界检查)：

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

这不是简单的尾递归(多个递归调用)，因此您必须添加某种堆栈结构来处理中间内存。一个版本看起来像这样(伪代码，java风格，同样，没有边界检查)：

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

伪代码：

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)

Answer 3

为此，我将使用Stack ou Queue对象。这是我的伪代码(类似python)：

stack.push(p0)
while stack.size() > 0:
    p = stack.pop()
    matrix[p] = 2
    for each point in Arround(p):
       if matrix[point]==0:
          stack.push(point)