Python 3.3.2 - 'Grouping' 字符系统

Question

我有一个有趣的小问题。

我需要计算文件中字符“组”的数量。假设该文件是...

..##.#..#
##..####.
.........
###.###..
##...#...

然后代码将计算 # 组的数量。例如，上面的内容是 3。它包括对角线。这是到目前为止我的代码:

build = []
height = 0
with open('file.txt') as i:
  build.append(i)
  height += 1
length = len(build[0])
dirs = {'up':(-1, 0), 'down':(1, 0), 'left':(0, -1), 'right':(0, 1), 'upleft':(-1, -1), 'upright':(-1, 1), 'downleft':(1, -1), 'downright':(1, 1)}

def find_patches(grid, length):
  queue = []
  queue.append((0, 0))
  patches = 0
  while queue:
    current = queue.pop(0)
    line, cell = path[-1]
    if ## This is where I am at. I was making a pathfinding system.

Answer 1

这是我想出的一个简单的解决方案。最初我只是想循环遍历所有元素一次，检查每个元素是否可以将其放入现有组中。但这不起作用，因为某些组只是稍后组合(例如，第二行中的第一个 # 直到该行中的第二个 # 才会属于大组已处理)。因此，我开始研究合并算法，然后认为我可以从一开始就这样做。

现在的工作原理是，我将每个 # 放入其自己的组中。然后我继续查看两个组的组合，并检查它们是否彼此足够接近，以至于它们属于同一组。如果是这种情况，我会将它们合并并重新启动检查。如果我完全查看了所有可能的组合并且无法再合并，我就知道我已经完成了。

from itertools import combinations, product
def canMerge (g, h):
    for i, j in g:
        for x, y in h:
            if abs(i - x) <= 1 and abs(j - y) <= 1:
                return True
    return False

def findGroups (field):
    # initialize one-element groups
    groups = [[(i, j)] for i, j in product(range(len(field)), range(len(field[0]))) if field[i][j] == '#']

    # keep joining until no more joins can be executed
    merged = True
    while merged:
        merged = False
        for g, h in combinations(groups, 2):
            if canMerge(g, h):
                g.extend(h)
                groups.remove(h)
                merged = True
                break

    return groups

# intialize field
field = '''\
..##.#..#
##..####.
.........
###.###..
##...#...'''.splitlines()
groups = findGroups(field)

print(len(groups)) # 3