如何在嵌套的 for 循环中使用 flood fill 来计算二维网格中 "rooms" 的数量？

Question

我正在尝试使用洪水填充算法来计算二维网格中“房间”的数量。我已经有了算法：

import sys

im = [list('...##########....................................'),
      list('...#........#....####..................##########'),
      list('...#........#....#..#...############...#........#'),
      list('...##########....#..#...#..........#...##.......#'),
      list('.......#....#....####...#..........#....##......#'),
      list('.......#....#....#......############.....##.....#'),
      list('.......######....#........................##....#'),
      list('.................####........####..........######')]

HEIGHT = len(im)
WIDTH = len(im[0])

def floodFill(image,x,y,newChar, oldChar = None):
        if oldChar == None:
            oldChar = image[y][x]
        if oldChar == newChar or image[y][x] != oldChar:
            return

        image[y][x] = newChar

        if y + 1 < HEIGHT and image[y + 1][x] == oldChar:
            floodFill(image, x, y + 1, newChar, oldChar)
        if y - 1 >= 0 and image[y - 1][x] == oldChar:
            floodFill(image, x, y - 1, newChar, oldChar)

        if x + 1 < WIDTH and image[y][x + 1] == oldChar:
            floodFill(image, x + 1, y, newChar, oldChar)
        if x - 1 >= 0 and image[y][x - 1] == oldChar:
            floodFill(image, x - 1, y, newChar, oldChar)
        return

def printImage(image):
    for y in range(HEIGHT):
        for x in range(WIDTH):
            sys.stdout.write(image[y][x])
        sys.stdout.write('\n')
    sys.stdout.write('\n')

我想做的是使用嵌套 for 循环来查找周期和运行算法，但我不确定如何成功调整 x 和 y 坐标当我运行浏览列表时。到目前为止我所拥有的是：

def loops(image):
    count = 0
    for i in image:
        for j in i:
            if j == '.':
                count += 1
                x =
                y =
                floodFill(image,x,y,'?',oldChar=None)

我的问题是，如何找到要放入函数中的周期的 x 和 y 坐标？

Answer 1

您可以使用 Python 的 built-in enumerate() 函数轻松确定所需的索引。你没问，不过我也建议你用它的print()函数输出图像，而不是直接写sys.stdout。除此之外，整个函数可以通过一次输出一整行来简化。

这是经过这些修改后的代码（以及我为使其更具可读性而进行的一些其他格式更改）。请注意，我认为您的 loops() 函数没有正确识别“房间”，但也不认为这是您询问的内容。

img = [list('...##########....................................'),
       list('...#........#....####..................##########'),
       list('...#........#....#..#...############...#........#'),
       list('...##########....#..#...#..........#...##.......#'),
       list('.......#....#....####...#..........#....##......#'),
       list('.......#....#....#......############.....##.....#'),
       list('.......######....#........................##....#'),
       list('.................####........####..........######')]

HEIGHT = len(img)
WIDTH = len(img[0])

def floodFill(image, x, y, newChar, oldChar=None):
        if oldChar == None:
            oldChar = image[y][x]
        if oldChar == newChar or image[y][x] != oldChar:
            return

        image[y][x] = newChar

        if y+1 < HEIGHT and image[y+1][x] == oldChar:
            floodFill(image, x, y+1, newChar, oldChar)
        if y-1 >= 0 and image[y-1][x] == oldChar:
            floodFill(image, x, y-1, newChar, oldChar)

        if x+1 < WIDTH and image[y][x+1] == oldChar:
            floodFill(image, x+1, y, newChar, oldChar)
        if x-1 >= 0 and image[y][x-1] == oldChar:
            floodFill(image, x-1, y, newChar, oldChar)
        return

def printImage(image):
#    for y in range(HEIGHT):
#        for x in range(WIDTH):
#            print(image[y][x], end='')
#        print()
#    print()
    for row in image:
        print(''.join(row))

def loops(image):
    count = 0
    for y, i in enumerate(image):
        for x, j in enumerate(i):
            if j == '.':
                count += 1
                floodFill(image, x, y, '?', oldChar=None)

loops(img)
printImage(img)

结果：

???##########????????????????????????????????????
???#????????#????####??????????????????##########
???#????????#????#??#???############???#????????#
???##########????#??#???#??????????#???##???????#
???????#????#????####???#??????????#????##??????#
???????#????#????#??????############?????##?????#
???????######????#????????????????????????##????#
?????????????????####????????####??????????######

如何在嵌套的 for 循环中使用 flood fill 来计算二维网格中 "rooms" 的数量？

How do I use flood fill in a nested for loop to count the number of "rooms" in a 2d grid?

python

flood-fill