1

Mi problema es el siguiente, tengo una matriz por ejemplo :

AAABBBC

ABBBCCA

BBCAAAA

Necesito saber cual es el mayor elemento de forma consecutiva perpendicularmente, en este caso seria B ya que sumando las B de forma perpendicular sumaría un total de 8 B.

Lo intenté obteniendo los indices y comparando los indices pero no logre resultado, también intente usar las filas como listas independientes y comparar los indices:

matriz = []
n=3
m=7
aux=[]


for i in range(n):
    matriz.append([])

    for j in range(m):
        matriz[i].append(input())
        if matriz[i][j] not in aux:
            aux.append(matriz[i][j])


def buscarElemento(lista, elemento):
    listaux = []
    for i in range(n):
        for j in range(m):
            if lista[i][j] == elemento:
                listaux.append([i,j])

    return(listaux)

def compare(elem1,elem2):
    conta=0


    if elem2[0] - elem1[0] == 1 and elem2[1]- elem1[1] == 0:

            conta+=1
    elif elem2[1] - elem1[1] == 1 and elem2[0]- elem1[0] == 0:
            conta+=1
    return conta


contador=1

for i in aux:

    lista = buscarElemento(matriz, i)
    print(lista)
    ini = lista[0]
    contador = 1
    for i in lista:
        cc = compare(ini, i)
        ini = i
        if cc==0:
            contador=1
        contador += cc

    print(contador)

Edición:

Siguiendo las recomendaciones de la respuesta de FJSevilla he llegado a esto:

matriz=['AAABBBC',
'ABBBCCA',
'BBCAAAA']
m=3
n=7
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):
    # 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 = buscarVecinos(f,c)

    for i, j in vecinos:
        if matriz[i][j] == value:         # Comprobamos si forma parte de la isla.
            d[id].append((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


d={}


for i in range(m):
    for j in range(n):
        if matriz[i][j]!=False:
            d[i,j]=[]
        id=i,j
        busqueda(i,j,'A',id)


print (d)

El problema ahora es que me sale el siguiente error:

TypeError: 'str' object does not support item assignment

EDIT: Solución gracias a FJSevilla obviamente un código mas desprolijo que su solución propia

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

matriz = [list(row) for row in matriz]
m= len(matriz) #filas
n= len(matriz[0]) #columnas
d={} #diccionario de manchas

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 < m and j >= 0 and j < n and matriz[i][j] == value)
    for i, j in vecinos:
        d[id].append((value,i, j))
        matriz[i][j] = False
        busqueda(i,  j,  value,  id)


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

result={}
max= 0
kmax=0
for key,  value in d.items():

        if len(value)>max:
            max=len(value)
            kmax=key[0]

print(kmax,',',max)
3
  • En realidad el problema no es más que una evolución del rancio problema de la isla, se puede resolver con menos de 20 líneas usando una aproximación del algoritmo DFS (búsqueda en profundidad). ¿Se supone que solo debemos tener en cuenta los elementos situados arriba, abajo, a la izquierda y a la derecha de un elemento dado? Es decir, ¿los vecinos situados en la diagonales no se tienen en cuenta?.
    – FJSevilla
    Commented el 17 may. 2017 a las 13:26
  • Claro, tengo que tener en cuenta los elementos de arriba, abajo, izquierda y derecha, las diagonales no se tienen en cuenta.
    – PCH
    Commented el 17 may. 2017 a las 22:37
  • He creado una respuesta donde planteo una forma de abordar el problema usando DFS. No me gusta dar el código sin más porque así no se aprende nada y le quita la "gracia" al asunto. Si quieres intentalo y si te atascas editas la pregunta con lo que estás intentando y te ayudo. Puede parecer complejo pero se puede implementar en unas 15-20 líneas sin problemas. Saludos.
    – FJSevilla
    Commented el 17 may. 2017 a las 23:41

1 respuesta 1

0

El problema puede parecer complejo pero en realidad es el problema de la isla un poco enrredado. Lo que nos piden es detectar la mayor isla pero con la salvedad de que una isla se define como elementos iguales que estan conectados vertical y horizontalmente.

Si tenemos la siguiente matriz:

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

Las islas serían:

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

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

La tarea consiste en encontrar esas seis agrupaciones. Para ello una forma de abordarlo es:

  • Primero de todo necesitamos una estructura de datos donde ir almacenado las 'islas'. Un diccionario es lo más simple, creamos una key única para cada 'isla' que encontremos y como valor agregamos los elementos que la componen (puede ser sus índice o solamente el recuento de elementos)

  • Recorremos cada elemento de la matriz (usando dos for), por cada uno:

    • Comprobamos que ese elemento no sea False (posteriormente veremos porqué).

    • Si ese elemento no es False significa que en el empieza una 'isla'. Creamos una nueva clave en el diccionario (podemos usar los indices del elemento para ello ya que son únicos). Por último, este elemento debe ser pasado a una función que haga una búsqueda en anchura.

La función que se encarga de implementar la DFS simplemente comprueba cada uno de los cuatro vecinos y por cada uno que tiene el mismo valor que el elemento pasado como parámetro ('A', 'B', etc) hace:

  • Cambia el valor de ese elemento a False en la matriz (marcar como visitado).

  • Agrega el elemento como parte de la 'isla' usando el diccionario de resultados con la key apropiada.

  • Se llama recursivamente con los parámetros de ese vecino para repetir la acción con sus propios vecino.

Esta función necesita recibir como parámetros, como mínimo, los indices del elemento al que aplicar la búsqueda y la clave correspondiente a esa 'isla' en el diccionario de resultados para que pueda ir agregando los elementos que encuentre.

Edición:

Te dejo la función encargada de la DFS casi completa a ver si te ayuda a aclarate algo:

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

El diccionario de resultados, en este caso guarda por cada isla un conjunto (set), con las tuplas de los índices de los elementos que la componen, por ejemplo:

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

Este sería el contenido del diccionario para guardar la cadena o isla de 'A' que empieza en el elemento matriz[0][0] de mi ejemplo. En este caso el la clave (id) de cada isla viene denotada por los índices del primer elemento que forma la isla, en este caso la "A" de (0, 0). Lo puedes construir con:

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

Donde i es la fila del elemento y la j la columna.

Edición 2:

Bién, tienes varios problemas en tu nuevo código. El error se debe a que intentas cambiar una cadena y estas son inmutables. Para poder modificar la matriz de esta forma necesitamos pasar de esto:

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

a esto:

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

En Python eso se hace simplemente con algo como:

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

Hecho esto, hay otro problema, en el ciclo for donde recorres la matriz debes llamar a busqueda() solo cuando el elemento no sea False, por otro lado, tal y como llamas a la función solo busca las 'A'.

El código debería ser algo así:

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)

Te dejo también la implementación original que hice yo, seguro que se puede mejorar pero aquí la dejo:

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

Realmente esto hace más de lo que necesitas ya que obtienes todas las cadenas que hay en la matriz y los elementos que las forman (sus indices dentro de ella). Si quitas el último break se imprimiran todas las cadenas y su longitud por orden.

6
  • Lo que me esta generando confusión es, recorro la matriz, genero una nueva clave en el diccionario si el elemento es distinto de False, y este elemento se lo paso a la función DFS, que recibiría como parámetros, los indices del elemento actual? O con la función que haga búsqueda de anchura te referís a la BFS. No entiendo muy bien que parametros pasarle a la DFS, si la clave de la isla que generé al ver que el elemento era distinto de False y el actual elemento de la matriz.
    – PCH
    Commented el 18 may. 2017 a las 3:32
  • DFS lo que hace es que pasado un elemento (sus indices en la matriz) busca los cuatro vecinos (arriba, abajo, derecha e izquierda). Si alguno es igual a valor del elemento pasado significa que es parte de la isla. En ese momento debe ir al diccionario y guardar ese elemnto en la clave del diccionario correspondiente a es isla y llamrse recursivamente. Por eso la función encargada de la DFS debe recibir los indices y la clave para la isla que está expandiendo.
    – FJSevilla
    Commented el 18 may. 2017 a las 11:23
  • @FrancoPachue voy a editar la pregunta y te dejo la estructura de la función encargada de la DFS, la función está casi completa, falta que solo que encuentres los índices de los cuatro vecinos, teniendo en cuenta que algunos elemntos (los de los bordes de la matriz) no tienen cuatro vecinos, sino menos. Aver si te ayuda a aclararte algo. Saludos.
    – FJSevilla
    Commented el 18 may. 2017 a las 11:28
  • La verdad que entendí bien el concepto, muchas gracias por la respuesta, edité el código poniendo la función de búsqueda de vecinos, el problema que tengo ahora es que en la sentencia en donde hago False al elemento en la matriz me salta el error siguiente: TypeError: 'str' object does not support item assignment EDIT: vi que tengo un error al momento de pasarle la id de la isla ya que le estoy pasando el i,j de cada uno, no la clave que debería corresponder.
    – PCH
    Commented el 18 may. 2017 a las 20:55
  • @FrancoPachue editada, mira a ver que tal. Te he dejado una implementación propia por si te interesa. He revertido parte de la edición de tu pregunta para mantener la lógica para que pueda ser útil a otros lectores. Cuando edites agregando nuevos estados de tu código, más si estan basados en respuestas es oportuno dejar lo anterior intacto para que la pregunta no quede sin sentido. Saludos.
    – FJSevilla
    Commented el 18 may. 2017 a las 21:33

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.