How to know if there are elements in a matrix followed horizontally and vertically in Python

The problem may seem complex but in reality it is the problem of the island a little tangled up. What they ask us is to detect the largest island but with the caveat that an island is defined as equal elements that are connected vertically and horizontally.

If we have the following matrix:

A A A B B A
A A B A B B
B B A A A A
B A B B B A

The islands would be:

A A A _ _ _     _ _ _ B B _     _ _ _ _ _ A
A A _ _ _ _     _ _ _ _ B B     _ _ _ _ _ _
_ _ _ _ _ _     _ _ _ _ _ _     _ _ _ _ _ _
_ _ _ _ _ _     _ _ _ _ _ _     _ _ _ _ _ _

_ _ _ _ _ _    _ _ _ _ _ _      _ _ _ _ _ _
_ _ B _ _ _    _ _ _ A _ _      _ _ _ _ _ _
_ _ _ _ _ _    _ _ A A A A      B B _ _ _ _
_ _ _ _ _ _    _ _ _ _ _ A      B B B B B _

The task is to find those six groupings. For this one way to address it is:

• First of all we need a data structure where the 'islands' are stored. A dictionary is the simplest, we create a unique key for each 'island' that we find and as a value we add the elements that compose it (it can be its index or only the count of elements)

• We go through each element of the matrix (using two for), for each one:

  • We check that the element is not False (we'll see why later).

  • If that element is not False it means that an 'island' starts at it. We create a new key in the dictionary (we can use the indices of the element for it since they are unique). Finally, this element must be passed to a function that makes a width search.

The function that implements the DFS simply checks each of the four neighbors and by each one that has the same value as the element passed as a parameter ('A', 'B', etc) does:

• Change the value of that element to False in the matrix (mark as visited).

• Add the element as part of the 'island' using the results dictionary with the appropriate key.

• It is called recursively with the parameters of that neighbor to repeat the action with its own neighbor.

This function needs to receive as parameters, at least, the indices of the element to which to apply the search and the key corresponding to that 'island' in the results dictionary so that it can be adding the elements it finds.

Edit:

I leave you the function in charge of the DFS almost complete to see if it helps you to clarify something:

def busqueda(f,  c,  value,  id):
    # f es la fila del elemnto
    # c la columna
    # value el valor del elemento('A', 'B', etc)
    # id es la clave de esa isla en el diccionario de resultados.

    # Solo falta encontrar los indices de los vecinos del elemento pasado
    # La lista de abajo deberia contener tuplas con los indices de los vecinos.
    # Por ejemplo, para f = 2 y c = 3 la lista debería ser:
    # vecinos = [(1, 3), (3, 3), (2, 2), (2, 4)]

    vecinos = []
    for i, j in vecinos:
        if matriz[i][j] == value:         # Comprobamos si forma parte de la isla.
            res[id].add((i, j))           # Anadimos el elemento al diccionario
            matriz[i][j] = False          # Marcamos como vistado ese elemento en nuestra matriz
            busqueda(i,  j,  value,  id)  # LLamada recursiva

The results dictionary, in this case, saves for each island a set ( set ), with the tuples of the indices of the elements that compose it, for example:

res = {"0:0": {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1)}}

This would be the content of the dictionary to store the string or island of 'A' that starts at the matriz[0][0] of my example. In this case the key (id) of each island is denoted by the indexes of the first element that forms the island, in this case the "A" of (0, 0). You can build it with:

"{}:{}".format(i, j)

Where i is the row of the element and j the column.

Edition 2:

Well, you have several problems in your new code. The error is because you try to change a string and these are immutable. To be able to modify the matrix in this way we need to move on from this:

matriz=['AAABBBC',
        'ABBBCCA',
        'BBCAAAA']

to this:

matriz=['A', 'A', 'A', 'B', 'B', 'B', 'C'],
       ['A', 'B', 'B', 'B', 'C', 'C', 'A'],
       ['B', 'B', 'C', 'A', 'A', 'A', 'A']]

In Python, that is simply done with something like:

matriz = [list[row] for row in matriz]

Once this is done, there is another problem, in the for cycle where you go through the matrix you should call busqueda() only when the element is not False , on the other hand, just as you call the function, just look for the 'A'.

The code should look something like this:

matriz=['AAABBBC',
'ABBBCCA',
'BBCAAAA']

matriz = [list(row) for row in matriz]
m= len(matriz)
n= len(matriz[0])

def buscarVecinos ( f,c):
    vecinos = []
    if (c > 0) :
        vecinos.append([f,c - 1])

    if (c < (n - 1)):
         vecinos.append([f,c+1])

    if (f > 0):
        vecinos.append([f - 1,c])

    if (f < (m - 1)):
        vecinos.append([f + 1,c])

    return vecinos

def busqueda(f,  c,  value,  id):
    vecinos = buscarVecinos(f,c)

    for i, j in vecinos:
        if matriz[i][j] == value:
            d[id].append((i, j)) 
            matriz[i][j] = False 
            busqueda(i,  j,  value,  id)

d={}

for i in range(m):
    for j in range(n):
        if matriz[i][j]:
            id=i,j
            d[i,j]=[]
            busqueda(i,j,matriz[i][j],id)
print (d)

I leave you also the original implementation that I did, sure it can be improved but here I leave it:

from collections import OrderedDict

matriz=['AAABBBC',
        'ABBBCCA',
        'BBCAAAA']

matriz = [list(row) for row in matriz]

filas =  len(matriz)
columnas = len(matriz[0])
res = {}

def busqueda(f,  c,  value,  id):
    vecinos = ((i, j) for i,  j in ((f-1,  c),  (f,  c-1),  (f,  c+1),  (f+1,  c))
                    if  i >= 0 and i < filas and j >= 0 and j < columnas and matriz[i][j] == value)
    for i, j in vecinos:
        res[id].add((i, j))
        matriz[i][j] = False
        busqueda(i,  j,  value,  id)


for f, row in enumerate(matriz):
    for c,  value in enumerate(row):
        if value:
            id = '{}:{}:{}'.format(value,  f,  c)
            res[id] = set([(f, c)])
            busqueda(f, c,  value,  id)

res = OrderedDict(sorted(res.items(), key=lambda x: len(x[1]), reverse = True))

for key,  value in res.items():
  print('{}: {} elementos.'.format(key.split(':')[0] ,len(value)))
  break

This really does more than what you need since you get all the chains that are in the matrix and the elements that form them (your indexes within it). If you remove the last break , all the strings and their length will be printed in order.