我有一个有趣的小问题。
我需要计算文件中字符“组”的数量。说文件是...
..##.#..#
##..####.
.........
###.###..
##...#...
然后,代码将计算#组的数量。例如,上面将是
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/