Python 用递归填充二维列表

Question

我需要写一个程序，能够递归地填充一个二维列表。这个列表就像一个网格，长得像这样：

I - I - I - - - 
I I - - - - - - 
I I I I - - - - 

然后用户会输入列和行的数字。程序接着会把那个区域的“-”替换成“@”。比如说，如果行是1，列是4，那么它看起来会像这样：

I - I @ I @ @ @
I I @ @ @ @ @ @
I I I I @ @ @ @ 

我必须用递归来实现这个功能。我现在只能让它部分填充一行。请帮帮我。

Answer 1

input_list = [['I', '-', 'I', '-', 'I', '-', '-', '-' ],
              ['I', 'I', '-', '-', '-', '-', '-', '-' ],
              ['I', 'I', 'I', 'I', '-', '-', '-', '-' ]]

def fill(x, y):
    if 0 <= x < len(input_list[0]) and 0 <= y < len(input_list) and input_list[y][x] == '-':
        input_list[y][x] = '@'
        fill(x, y + 1)
        fill(x, y - 1)
        fill(x + 1, y)
        fill(x - 1, y)
    return

这个代码会通过移动到四个邻居的位置来寻找一个可以填充的点。

要注意，这里使用的是x-y坐标（从0开始计数）。所以如果你想用行列坐标（从1开始计数），只需要这样转换：

fill(column - 1, row - 1)

Answer 2

这个程序其实很简单，如果你从网格的右下角开始，然后向回递归到(0, 0)的位置。我们一步一步来看看这个逻辑：

• 我们从右下角开始，在你的例子中是(2, 7)。你需要填充所有大于你的边界的部分，在你的例子中是(0, 3)。这些就是我们在递归方法中需要的参数。

  recur_fill(input_list, a, b, i, j)
  

• 接下来，我们要设置边界条件。你的程序只需要在坐标大于零的时候执行。也就是说，如果 i < 0 或 j < 0，我们就得停止。这可以理解为：

  if i < 0 or j < 0:
      return
  

• 现在，我们需要处理涂色的边界，也就是a和b。只要我们的坐标大于你的边界，我们就需要检查这个单元格是否是 -，如果是，就用 @ 填充它。这可以理解为：

  if i >= a and j >= b:
      if input_list[i][j] == '-':
          input_list[i][j] = '@'
  

• 接下来，我们需要递归地填充这些单元格，直到所有符合条件的单元格都被填满。也就是说：

  recur_fill(input_list, a, b, i - 1, j)
  recur_fill(input_list, a, b, i, j - 1)
  

总结一下，我们得到：

from pprint import pprint

def recur_fill(input_list, a, b, i, j):
    if i < 0 or j < 0:
        return

    if i >= a and j >= b:
        if input_list[i][j] == '-':
            input_list[i][j] = '@'

    recur_fill(input_list, a, b, i - 1, j)
    recur_fill(input_list, a, b, i, j - 1)

def main():
    input_list = [['I', '-', 'I', '-', 'I', '-', '-', '-' ],
                  ['I', 'I', '-', '-', '-', '-', '-', '-' ],
                  ['I', 'I', 'I', 'I', '-', '-', '-', '-' ]]
    recur_fill(input_list, 0, 2, 2, 7)
    pprint(input_list)


if __name__ == '__main__':
    main()