我有一个有趣的小问题。

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

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


然后,代码将计算#组的数量。例如,上面将是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.

最佳答案

这是我想出的一个简单的解决方案。最初,我只是想遍历所有元素,如果可以将其放入现有组中,则对每个元素进行一次检查。但是,这没有用,因为某些组仅在以后合并(例如,第二行中的第一个#在处理完该行中的第二个#之后才属于大组)。所以我开始研究合并算法,然后想到我可以从一开始就做到这一点。

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

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

关于python - Python 3.3.2-带字符的“分组”系统,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18568678/

10-14 19:23
查看更多