Subscribe:

viernes, 30 de diciembre de 2016

Matriz caracol en C++

Cuando recién entré a la universidad recibí un curso propedéutico de parte de un profesor y un par de alumnos de (en ese entonces) tercer semestre. En dicho curso nos pusieron varios ejercicios de programación, entre los cuales hubo uno que no puse resolver por más que intenté.

Pasó el tiempo y olvidé que no lo había resuelto, pero hoy mientras cavilaba lo recordé y se me ocurrió ver si ya era capaz de resolverlo. El problema en sí es sencillo, pero para los conocimientos que tenía en aquel entonces no me sorprende que no lo pudiese resolver.

El problema es "La matriz caracol", que no es más que imprimir una matriz de tal manera que los números sigan una espiral (Ya sea de afuera hacia adentro o viceversa).

El método que usé para resolverlo, después de pensar un rato, fue un DFS en vecindad 4. El DFS recibe la posición de la matriz en que va a buscar, el valor que le asignará a la posición en caso de que esta no haya sido visitada antes y la posición de búsqueda en que se mandó a llamar la función, las posiciones de la vecindad 4 las definí en un vector de tuplas y es tal cual (en formato de tupla (y, x)) vPos = [(0, 1), (1, 0), (0, -1), (-1, 0)].

La imagen anterior representa el índice de las posiciones según el vector antes mencionado. Como el recorrido de la matriz cambia de dirección en sentido de las manecillas de reloj (izquierda -> derecha, arriba -> abajo, derecha -> izquierda, abajo -> arriba), también lo debe hacer el comienzo de la búsqueda para quedar acorde a la dirección del recorrido, es por esto que la siguiente llamada a la función del DFS comienza la búsqueda en el mismo sentido que el recorrido actual de la matriz. Se puede tomar la imagen anterior como la búsqueda siguiendo la dirección izquierda -> derecha, las siguientes 3 imágenes son arriba -> abajo, derecha -> izquierda y abajo -> arriba, respectivamente.

Esperando que la explicación anterior sea clara, el código es el siguiente:

Entre las cosas que se pueden mejorar se me ocurre que se puede usar otro mejor método para recorrer las posiciones al igual que otra comparación menos pinche. El programa lee un número entero positivo que es el tamaño de lado de la matriz (Es una matriz cuadrada) y a partir de eso crea la matriz caracol de afuera hacia adentro, creo que no es mucho trabajo hacer que funcione al revés.

Cabe mencionar que debe compilarse usando C++11 o posteriores (porque uso auto en el foreach y tuplas). Un ejemplo de la salida del programa es el siguiente:

Bueno, esta es mi propuesta de solución para ese problema que me dejaron hace ya varios años y que en su momento no supe resolver. Si alguien tiene otra propuesta de solución agradecería que la compartan.

Hasta luego.

0 Comentarios:

Publicar un comentario