2

Tengo una matriz nxm , donde cada celda debe ser de dimensiones A * A. Los datos de la matriz se rellenan con unos(1) y ceros(0), ejemplo:

[ 1, 1, 1, 1, 1]
[ 0, 1, 1, 0, 1]
[ 0, 1, 0, 0, 1]
[ 0, 1, 1, 1, 1]
[ 0, 1, 0, 0, 1]
[ 0, 1, 1, 1, 1]
[ 0, 0, 0, 0, 0]
[ 1, 1, 1, 1, 1]
[ 1, 1, 0, 0, 1]
[ 1, 1, 1, 1, 1]

Teniendo las estructuras:

typedef struct Punto{
     int x, int y;
} Punto;

typedef struct Poligono{
     Puntos vertices;
     int    total;
} Poligono;

Deseo conseguir dos funciones tales que:

int totalPoligonos = 0, totalHuecos = 0; 
Poligono *poligonos = buscarPoligonos(matriz, &totalPoligonos);
Poligono *HuecosPoligonos = buscarPoligonos(matriz, &totalHuecos);

Los puntos deben calcularse en base a la constante A.

No existen nada de diagonales, sólo polígonos irregulares con formas rectangulares XD que están delimitados por las celdas con valor 1.

El problema en sí, es saber como recorrer el perímetro. Estaba pensando en tener una lista enlazada, para ver que casillas he recorrido, pero me quedo corto al momento en que una casilla con valor uno se encuentre rodeadas por uno, mas o menos ese es el algoritmo que pretendo implementar, pero he quedado corto de ideas.

4
  • No queda claro lo que preguntas. ¿ Que es un polígono ? ¿ solo rectángulos, o valen diagonales ?. Además de lo anterior, ¿ que llevas hecho ? ¿ Donde te has atascado ? Aquí no se hacen deberes.
    – Trauma
    el 11 ene. 2017 a las 4:58
  • Ahí es donde estoy atascado no se como abordar el problema, no pido código, solo mas o menos como podría ser el algoritmo naturalmente hablando XD, No existen nada de diagonales, sólo polígonos irregulares con formas rectangulares XD que están delimitados por las celdas con valor 1. el 11 ene. 2017 a las 5:19
  • El problema en sí, es saber como recorrer el perímetro. Estaba pensando en tener una lista enlazada, para ver que casillas he recorrido, pero me quedo corto al momento en que una casilla con valor uno se encuentre rodeadas por uno, mas o menos ese es el algoritmo que pretendo implementar, pero como he dicho he quedado corto de ideas. el 11 ene. 2017 a las 5:24
  • Es mas facil de lo que crees. Espera que te monto una respuesta. El truco no está en los 1, sino en los 0.
    – Trauma
    el 11 ene. 2017 a las 5:27

1 respuesta 1

1

Como indiqué en el comentario, el truco está en buscar los 0. Es un ejercicio de recursividad.

Cada 0 divide la matriz en 8 submatrices.

11111111   1111 111              1
11111111   1111 111              1
    0      11110111   11110111   0
11111111   1111 111              1
11111111   1111 111              1

Esos serian los regtángulos mas grandes que podrian existir, si no tienen, a su vez, 0 internos.

Puedes hacer una funcion que se llame recursivamente, y que devuelva esas 8 submatrices para cada matriz pasada como argumento.

2
  • Una cosita rapida. Despues tendrías que sumar los rectangulos resultantes, buscando el mayor posible.
    – Trauma
    el 11 ene. 2017 a las 5:54
  • 1
    Gracias, entendido al 100%. el 11 ene. 2017 a las 6:02

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.