I have a list like this:

a=[
   ["x", "x", 0,  0, "x", "x"],
   [ 0,   0,  0,  0, "x", "x"],
   ["x", "x", 0,  0,  0,  "x"],
   ["x", "x", 0,  0,  0,   0 ]
]

Q1:
I want any of the x in list that are connected to each other be in a group

Example:

1. group 1 = (0,0),(0,1)

2. group 2 = (0,4),(0,5),(1,4),(1,5),(2,5)

3. group 3 = (2,0),(2,1),(3,0),(3,1)

"What is the solution?"

Q2:
And how do i know which path is shortest between the two groups

CodePudding user response：

For Q1, you can go through the matrix row by row and column by column forming groups with sets associated with the coordintate. Place each coordinate in the set of the connecting positions above or to the left of the current one. Create a new set (group) when there are no connections, Merge the sets when both are connected.

a=[
   ["x", "x", 0, 0, "x","x"],
   [ 0,   0,  0, 0, "x","x"],
   ["x", "x", 0, 0,  0, "x"],
   ["x", "x", 0, 0,  0,  0 ]
]

groups = dict()                    # group (set) at each coordinate
for r,row in enumerate(a):
    for c,v in enumerate(row):
        above = groups[r-1,c] if r and a[r-1][c] == v else None     
        left  = groups[r,c-1] if c and a[r][c-1] == v else None
        if above and left:         
            for rc in left:        # merge left into above group
                groups[rc] = above 
                above.add(rc)
        g = above or left or set() # select existing group or new
        g.add((r,c))               # add r,c to selected group
        groups[r,c] = g            # identify coordinate's group

# extract distinct groups from coordinate assignments
groups = list({id(g):[*g] for g in groups.values()}.values())

Output:

# all groups (i.e. groups of "x"s and groups of 0s)
print(groups)
[[(0, 1), (0, 0)], 
 [(1, 2), (3, 2), (1, 3), (3, 5), (3, 3), (0, 2), 
  (2, 4), (2, 3), (2, 2), (1, 0), (3, 4), (1, 1), (0, 3)], 
 [(1, 4), (1, 5), (0, 5), (0, 4), (2, 5)], 
 [(3, 0), (2, 0), (3, 1), (2, 1)]]

# only "x" groups
xGroups = [g for g in groups if a[g[0][0]][g[0][1]] == "x"]
print(xGroups)
[[(0, 1), (0, 0)], 
 [(1, 4), (1, 5), (0, 5), (0, 4), (2, 5)], 
 [(3, 0), (2, 0), (3, 1), (2, 1)]]

For Q2, you can write a function that will find the distance between two groups by expanding on the paths that each coordinate of the first group can go through to reach any coordinate of the second group while only going through 0 positions (technically a breadth-first search):

def distance(a,g1,g2):
    rows = len(a)
    cols = len(a[0])
    distance = 1
    seen     = set(g1) # track visited coordinates
    paths    = g1      # current reach, starts with g1 coordinates
    while paths:
        nextPaths = set()
        for r,c in paths:
            for nr,nc in [(r,c-1),(r,c 1),(r-1,c),(r 1,c)]: #neighbours
                if nr not in range(rows): continue
                if nc not in range(cols): continue
                if (nr,nc) in seen: continue        # no doubleback
                if (nr,nc) in g2: return distance   # g2 reached
                if a[nr][nc] == 0:
                    nextPaths.add((nr,nc))          # advance on 0s
                    seen.add((nr,nc))
        distance  = 1                  # g2 not reached, need more steps
        paths = nextPaths              # start from positions reached so far
    return None

print(distance(a,xGroups[0],xGroups[1])) # 3
print(distance(a,xGroups[1],xGroups[2])) # 4            
print(distance(a,xGroups[0],xGroups[2])) # 2