# Propuesta de ejercicios - Maratón Nacional ACM
> Realizado por el grupo GUMP de ACMUD
## A. Turismo peresozo
Un grupo de turistas llega a una ciudad y se dispone a encontrar un hotel en el cual todos puedan pasar la noche. Pero debido al cansancio por el viaje solo están dispuestos a desplazarse un número específico de kilometros como máximo. Abren [hotel.acm.org](https://hackmd.io/@PB203/SyQqp5aqa), ya que saben que en esta página se pueden encontrar hoteles introduciendo tres parámetros:
* La localización $L$ (en coordenadas)
* La cantidad $t$ de habitaciones esperadas
* La cantidad máxima $m$ de kilometros que esperan desplazarse
La página les ofrece buscar a la redonda o buscar en área cuadrada, en cualquier caso cualquier hotel encontrado estará máximo a una distancia $m$ de kilometros de la ubicación $L$ ingresada y tendran como mínimo $t$ vacantes disponibles.
Deciden que para desplazarse lo menos posible buscarán en un área cuadrada y así pronto encuentran varios hoteles que cumplen con sus criterios.
Uno de los turistas (menos perezoso que sus demás compañeros) se interesa por saber cómo [hotel.acm.org](https://hackmd.io/@PB203/SyQqp5aqa) logra encontrar tales hoteles en un área cuadrada y decide desarrollar por su propia cuenta una versión del algoritmo de la página. ¿Podría usted realizar esta misma tarea?
### Entradas
Para cada caso se tendrá una ciudad cuadrada de $16(10^3)$ kilometros de largo. La primera línea de cada caso contendrá un entero $h$ ($0 \leq h \leq 256(10^6)$) que indica la cantidad de hoteles con disponibilidad en la ciudad.
Las siguientes $h$ líneas contendrán tres enteros $i$, $j$, $v$ ($0 \leq i, j \leq 16(10^3); 0 < v < 10^2$). Cada línea representa la posición $(i, j)$ de un hotel con sus respectivas $v$ habitaciones disponibles. En un plano ordenado $i$ y $j$ son los kilometros hacia la derecha y hacia abajo, respectivamente, entre la esquina superior izquierda de la ciudad y el hotel.
La siguiente línea representa la cantidad $T$ ($0 \leq T \leq 10^6$) de búsquedas realizadas en un mismo instante en [hotel.acm.org](https://hackmd.io/@PB203/SyQqp5aqa).
Las siguientes $T$ líneas contendrán dos reales positivos y dos enteros $x$, $y$, $t$, $m$ ($0 \leq x, y \leq 16(10^3); 0 < t < 10^2; 0 < m \leq 8(10^3)$). Cada línea representa la posición $(x, y)$ de un grupo de turistas. $t$ es el número de habitaciones de hotel que necesita ese grupo y $m$ es el número máximo de kilometros que está dispuestos a desplazarse ese grupo. En un plano ordenado $x$ y $y$ son los kilometros hacia la derecha y hacia abajo, respectivamente, entre la esquina superior izquierda de la ciudad y el hotel.
El último caso se caracteriza por que se ingresa una ciudad con ```0``` hoteles y ```0``` búsquedas realizadas. En cualquier otro caso se debe procesar la solicitud.
### Salidas
Para cada búsqueda en que se encuentre al menos un hotel que cumpla con los criterios solicitados por los turistas, debe imprimirse en pantalla una línea con el índice de cada hotel (el índice del primer hotel ingresado para la ciudad es ```1```). Los índices deben ir separados por comas sin espacios.
En caso de no encontrar ni un hotel que cumpla con los criterios de búsqueda se debe imprimir en pantalla en una línea el siguiente mensaje:
```ACM no encontro hoteles con sus criterios```
Al acabar un caso debe imprimirse una un guión ```-``` en una nueva línea. El último caso, como no debe procesarse, no devolverá ningún mensaje.
### Ejemplos
#### Entradas
```
2
3 1 5
7 1 5
4
4.5 3 4 3
6 5 4 5
6 4 4 5
1 7 4 4
2
0 1 4
3 1 5
2
1.5 0 4 5
2.5 2 5 2
0
0
```
#### Salidas
```
1
ACM no encontro hoteles con sus criterios
2,1
ACM no encontro hoteles con sus criterios
-
2,1
2
-
```
### Solución propuesta
Este problema puede ser resuelto utilizando Quadtrees: estructuras de datos usadas para representar eficientemente espacios bidimensionales. La técnica consiste en segmentar recursivamente el área (nodo) en cuadrantes (hijos) de manera que cada punto de interés en la superficie ocupe una hoja del árbol.
Un árbol de profundidad $d$ que contenga $n$ puntos contendrá $\mathcal{O}\left(\left(d+1\right)n\right)$ nodos y puede ser construído en $\mathcal{O}\left(\left(d+1\right)n\right)$ tiempo; para una superficie con puntos distribuídos equitativamente, $d=\left\lceil\textrm{log}_4\left(n\right)\right\rceil$, pero puntos muy cercanos entre sí aumentarán la altura, lo que podría resultar en un árbol desbalanceado.
Cada nodo del árbol contiene:
* Límites del nodo (derecha, izquierda, arriba, abajo).
* Hoteles contenidos, ordenados de mayor a menor capacidad.
* Nodos contenidos.
Donde cada hotel contiene coordenadas y capacidad.
Para cada consulta (grupo de turistas) se seguirá el siguiente procedimiento:
1. Definir un área cuadrada $A$ con centro en $\left(x,y\right)$ y lado $\frac{2m}{\sqrt{2}}$.[^m]
2. Identificar todos los nodos que intersectan con $A$. Esta operación tiene complejidad $\mathcal{O}\left(\textrm{log}\left(n\right)\right)$.
3. Para cada hotel de cada nodo, imprimir los hoteles donde $\textrm{dist}\left(\left(i, j\right), \left(x,y\right)\right)\le m$ y $t\le v$. Esta operación es de complejidad $\mathcal{O}\left(n\cdot\textrm{log}\left(n\right)\right)$.
4. Si se encuentra un hotel tal que $t>v$, pasar al siguiente nodo.
---
[^m]: Se entiende que si la máxima distancia recorrida es $m$, esta tiene que ser la distancia a la esquina del área cuadrada a utilizar. Entonces $m$ es la hipotenusa de un triangulo rectangulo con un vertice en en centro del área cuadrada y otro vertice en la esquina de esta área. Finalmente, por pitagoras se deduce que la distancia entre la locacion $L$ y los limites del cuadrado horizontal y verticalmente es $\frac{m}{\sqrt{2}}$ y el lado completo del área cuadrada es $\frac{2m}{\sqrt{2}}$.
## C- Inversiones de Roche
Roche, una famosa empresa de inversiones tiene tres posibles inversiones para interesados como usted. Cada una tiene una probabilidad de retorno de efectivo al finalizar el año y es su labor invertir adecuadamente el dinero del que dispone para maximizar su ganancia año tras año.
Roche ofrece una tabla como la siguiente cada año, para que los interesados obtengan información sobre sus oportunidades de inversión:
| Inversión | Costo de inversión al iniciar el año | Retorno de dinero y probabilidad |
| :- | :- | -: |
| Academía de Danza | $5000 | $0 (30%) <br> $10000 (70%) <tr></tr> |
| Casa-museo regional | $5000 | $5000 (90%) <br> $10000 (10%) <tr></tr> |
| Manglar Lizza's | $7000 | $3000 (25%) <br> $7000 (50%) <br> $10000 (25%) |
Suponga que los valores y las probabilidades de retorno no se alteran al pasar de los años y que desea invertir año tras año en a lo mucho una inversión de su elección (puede elegir una nueva cada año tras obtener su retorno). Elabore una estrategia de inversión óptima que le permita prosperar por $n$ años o no invertir en nada desde el principio (unicamente si puede asegurar que ninguna otra opción es beneficiosa).
### Entradas
Para cada caso, la primera línea contendrá dos enteros $P$ y $n$ ($0 \leq P \leq 10^4; 0 \leq n \leq 10^2$) que son respectivamente su presupuesto al iniciar el primer año y la cantidad de años máxima en los que va a invertir.
Las siguientes líneas serán la información para las inversiones $A$, $C$ y $M$, para las cuales cada línea empezará indicando a qué inversión pertenece con un simple carácter en mayúscula (A, C o M). Luego se encontrarán dos enteros y un real $c$, $r$, $p$ ($0 \leq c,r \leq 10^4; 0 \leq p \leq 1$) donde $c$ es el costo de la inversión al iniciar el año, $r$ es un valor de retorno de esa inversión y $p$ es la probabilidad de ese retorno.
Finalmente, la última línea de cada caso contendrá un sencillo ```-``` (guión) para marcar que allí acaba dicho caso.
Para todo caso se asegura que la información no va a resultar contradictoria y siempre va a estar completa, pero puede que las líneas de información para una inversión particular (ej. A) no sean continuas.
El último caso se indica con dos ceros separados por un espacio.
### Salidas
Para cada caso, si existe una inversión óptima a realizar el primer año, se debe imprimir un indicador (A, C o M), un entero y un real $i$, $v$ ($0 \leq i \leq 10^4; 0 < v \leq 1$) en una misma línea separados por espacios. $i$ será el valor a invertir el primer año y $v$ será la viabilidad (en valor porcentual con un máximo de 6 decimales truncados) óptima para no tener perdidas al pasar como máximo los $n$ años planteados al inicio del problema.
En caso que todas las inversión conlleven a una pérdida de dinero con respecto al presupuesto $P$, se debe imprimir en pantalla ```Significa pérdidas```
En caso que exista más de una inversión óptima con la misma probabilidad se debe imprimir en pantalla ```Es indecidible```.
Para el último caso debe imprimirse en pantalla ```Es indefinido```.
### Ejemplos
#### Entradas
```
5000 3
A 5000 0 0.3
A 5000 10000 0.7
C 5000 5000 0.9
C 5000 10000 0.1
M 7000 3000 0.25
M 7000 7000 0.5
M 7000 10000 0.25
-
1000 5
A 1000 0 0.9
C 500 100 0.1
M 500 100 0.3
A 1000 0 0.05
A 1000 0 0.05
C 500 100 0.5
M 500 100 0.7
C 500 100 0.4
-
1200 2
A 1000 1100 0.5
C 500 100 0.3
M 500 600 0.25
M 500 550 0.75
C 500 0 0.7
A 1000 0 0.5
-
10000 5
A 5000 7000 1
C 5000 9000 0.6
C 5000 6000 0.4
M 7000 1000 1
M 7000 0 0
-
0 0
```
#### Salidas
```
A 5000 0.342000
Significa pérdidas
Es indecidible
A 5000 1.000000
Es indefinido
```
### Solución propuesta
Este problema se puede afrontar a través de programación dinámica probabilística. Para ello se identificarán los elementos propios de la PDP.
$$ m: número\ de\ años\ transcurridos = {1, 2, 3, ..., n} $$ $$ X_m: inversión\ realizada\ el\ m-esimo\ año = {A, C, M}$$ $$ S_m: presupuesto\ al\ m-esimo\ año $$ $$ f_m: función\ de\ probabilidad\ al\ m-esimo\ año $$ $$f_m(S_m, X_m) = \sum_{i=1}^{k} p_{X_{m_i}} f^*_{m+1}(S_m - C_{X_{m_i}} + r_{X_{m_i}}) $$
Una vez definida la función $f_m$ podemos observar que para una decisión $X_{m_i}$, el valor de $S_{m+1}$ es:
$$S_{m+1}(X_{m_i}) = S_m - C_{X_{m_i}} + r_{X_{m_i}} = S_m + (r_{X_{m_i}} - C_{X_{m_i}}) $$ $$ g(X_m) = \underset{r_{X_{m_i}} - C_{X_{m_i}}}{max} (r_{X_{m_i}} - C_{X_{m_i}}) $$ $$ h(X_m) = \underset{r_{X_{m_i}} - C_{X_{m_i}}}{min} (r_{X_{m_i}} - C_{X_{m_i}}) $$
Esta analisis es útil para darse cuenta que en un estado $S_m$ tomar una decisión $X_m$ hace aumentar el presupuesto como máximo una cantidad $g(X_m)$ y como mínimo una cantidad $h(X_m)$ ambas con su respectiva probabilidad $p_{X_{m_i}}$. Esto servirá más adelante para determinar rápidamente que decisión realizar y obtener el valor al tomar una decisión $X_m$ teniendo en cuenta su coste, su retorno y su probabilidad.
Ahora, por PDP sabemos que el límite para determinar que una inversión no es una perdida al pasar $n$ años es si el presupuesto en el momento ($S_n$) es mayor o igual al presupuesto al iniciar la inversión. Por tal concluimos que:
$$ f_n(S_n)=\left\{\begin{matrix}0 & S_n < P \\ 1 & S_n \geq P \end{matrix}\right. $$
Luego, consideremos que al llegar al último año para el cual podemos invertir ($n$) contamos con un presupuesto mayor al presupuesto inicial. Para este punto invertir es innecesario (es opcional, pero basado en el PDP el resultado de invertir es siempre suboptimo en $n$, así que se considera evidente que lo optimo es no invertir)
Consideremos que al año $n$ se llega con un presupuesto menor al presupuesto inicial, entonces toca analizar si alguna de las inversiones puede hacer que superemos el presupuesto inicial. Para ello se puede usar la fórmula $S_{m+1}(X_{m_i})$ y ver qué si decidimos una inversión $X_n$, abra una probabilidad $p_{X_{n_i}}$ de que el valor aumente como mínimo $h(X_n)$ unidades. Notese que sin importar que tan distante este nuestro presupuesto de $P$, si existe una decisión $X_n$ tal que nuestro presupuesto final ($S_n$) sea mayor a $P$, el valor de $g$ para esta decisión es el optimo o existe una decisión con un valor $g$ mayor tal que esa es la optima y su probabilidad es $p_{g(X_n)}$.
Ya que $g$ depende únicamente de la decisión tomada, sin importar el estado $S_m$, entonces la distancia minina para que el presupuesto final supere o igualé al presupuesto inicial es $h$ y la distancia máxima es $g$, para ambos casos el optimo es $g$. Estos valores pueden calcularse desde el inicio del ejercicio y se mantendran constantes hasta el final del mismo.
Finalmente, el último caso es cuando no existe inversión que permita que el presupuesto final supere o iguale el inicial. ese caso se da si no existe $g$ para ninguna decisión $X_n$ que satisfaga las condiciones.
Expresando lo anterior de la forma en que se expresan las soluciones PDP, se tiene la tabla:
| $S_n$ | $X^*_n$ | $f^*_n$ |
| :-: | :-: | :-: |
| $S_{n-1} \geq P$ | -- | $1$ |
| $S_{n-1} + g(X_m) \geq P \geq S_{n-1} + h(X_m)$ | $X_m$ | $p_{g(X_m)}$ |
| $S_{n-1} + g(X_m) < P$ | -- | $0$ |
Ahora bien, de manera similar se pueden plantear la siguiente tabla de PDP. Para ella basta con tener en cuenta los siguientes tres casos:
1. Cuando existe un valor de $h$ que es suficiente para que $S_{n-1}$ quede por encima de $P$
2. Cuando existe un valor de $g$ que es suficiente para que se necesite a lo mucho un valor $g$ para alcanzar $P$ (esto coincide con un único caso de la primera tabla PDP)
3. Cuando no existe un valor de $g$ tal que se necesite a mucho otro $g$ para alcanzar $P$ el presupuesto final.
Expresando lo anterior en una tabla PDP se tiene:
| $S_{n-1}$ | $X^*_{n-1}$ | $f^*_{n-1}$ |
| :-: | :-: | :-: |
| $S_{n-2} + h(X_m) \geq P$ | $X_m$ | $p_{g(X_m)}$ |
| $S_{n-2} + 2g(X_m) \geq P \geq S_{n-2} + 2h(X_m)$ | $X_m$ | $(p_{g(X_m)})^2$ |
| $S_{n-2} + 2g(X_m) < P$ | -- | $0$ |
A partir de aquí se puede desarrollar por PDP la solución para varios años hasta llegar al primer año ($m=1$), para el cual su respectiva tabla PDP es:
| $S_1$ | $X^*_1$ | $f^*_1$ |
| :-: | :-: | :-: |
| $(n-1)h(X_m) \geq 0$ <br> $h(X_m) \geq 0$ | $X_m$ | $(p_{g(X_m)})^{(n-1)}$ |
| $n\ g(X_m) \geq 0 \geq n\ h(X_m)$ <br> $g(X_m) \geq 0 \geq h(X_m)$ | $X_m$ | $(p_{g(X_m)})^n$ |
| $n\ g(X_m) < 0$ <br> $g(X_m) < 0$ | -- | $0$ |
Finalmente se tiene la probabilidad de viabilidad para una decisión $X_m$. Comparando todas las decisiones se puede determinar si significan perdidas, si tienen viabilidad igual o si hay una que sea optima.
## M) Memento Mori
En el escritorio de un viejo desarrollador de videojuegos kamikaze se hallan unos diagramas ordenados en una carpeta rotulada como __*Memento Mori*__. Los diagramas describen un juego en el que un personaje debe hallar un camino óptimo a un punto seguro marcado con una bandera, evitando pasar por bombas posicionadas en el terreno. El siguiente es un diagrama de la carpeta etiquetado como tutorial.
```vega
{
"$schema": "https://vega.github.io/schema/vega-lite/v5.json",
"description": "Diagram",
"height": 300,
"width": 300,
"padding": {
"top": 0,
"left": 150,
"right": 150,
"bottom": 10
},
"data": {
"values": [
{"row": 1, "col": 1, "type": "flag"},
{"row": 2, "col": 1, "type": "space"},
{"row": 3, "col": 1, "type": "space"},
{"row": 1, "col": 2, "type": "bomb"},
{"row": 2, "col": 2, "type": "bomb"},
{"row": 3, "col": 2, "type": "space"},
{"row": 1, "col": 3, "type": "space"},
{"row": 2, "col": 3, "type": "user"},
{"row": 3, "col": 3, "type": "space"}
]
},
"mark": {
"type": "point",
"filled": true
},
"encoding": {
"x": {
"field": "col",
"type": "ordinal",
"axis": null
},
"y": {
"field": "row",
"type": "ordinal",
"axis": null
},
"shape": {
"field": "type",
"type": "nominal",
"scale": {
"domain": [
"flag", "space", "bomb", "user"
],
"range": [
"M 0.855469 0.375 C 0.855469 0.167969 0.664062 0 0.429688 0 C 0.191406 0 0 0.167969 0 0.375 L 0 5.625 C 0 5.832031 0.191406 6 0.429688 6 C 0.664062 6 0.855469 5.832031 0.855469 5.625 L 0.855469 4.125 L 1.71875 3.9375 C 2.269531 3.816406 2.851562 3.871094 3.359375 4.09375 C 3.949219 4.351562 4.636719 4.382812 5.257812 4.179688 L 5.722656 4.027344 C 5.890625 3.972656 6 3.832031 6 3.675781 L 6 0.773438 C 6 0.503906 5.675781 0.328125 5.398438 0.449219 L 5.269531 0.507812 C 4.652344 0.777344 3.921875 0.777344 3.300781 0.507812 C 2.832031 0.300781 2.292969 0.25 1.78125 0.359375 L 0.855469 0.5625 Z M 0.855469 0.375",
"",
"M 5.378906 0.613281 L 5.1875 0.078125 C 5.164062 0.03125 5.117188 0 5.0625 0 C 5.011719 0 4.964844 0.03125 4.941406 0.078125 L 4.75 0.613281 L 4.210938 0.8125 C 4.160156 0.828125 4.125 0.878906 4.125 0.933594 C 4.125 0.984375 4.160156 1.035156 4.210938 1.050781 L 4.746094 1.25 L 4.941406 1.785156 C 4.960938 1.835938 5.007812 1.875 5.0625 1.875 C 5.117188 1.875 5.167969 1.835938 5.183594 1.785156 L 5.378906 1.25 L 5.914062 1.050781 C 5.964844 1.035156 6 0.984375 6 0.933594 C 6 0.878906 5.964844 0.828125 5.914062 0.8125 Z M 3.828125 1.234375 C 3.683594 1.089844 3.445312 1.089844 3.296875 1.234375 L 3.265625 1.269531 C 3.007812 1.175781 2.726562 1.125 2.4375 1.125 C 1.089844 1.125 0 2.214844 0 3.5625 C 0 4.910156 1.089844 6 2.4375 6 C 3.785156 6 4.875 4.910156 4.875 3.5625 C 4.875 3.273438 4.824219 2.992188 4.730469 2.734375 L 4.765625 2.703125 C 4.914062 2.554688 4.914062 2.316406 4.765625 2.171875 Z M 2.34375 2.25 C 1.671875 2.25 1.125 2.796875 1.125 3.46875 L 1.125 3.5625 C 1.125 3.664062 1.039062 3.75 0.9375 3.75 C 0.835938 3.75 0.75 3.664062 0.75 3.5625 L 0.75 3.46875 C 0.75 2.589844 1.464844 1.875 2.34375 1.875 L 2.4375 1.875 C 2.539062 1.875 2.625 1.960938 2.625 2.0625 C 2.625 2.164062 2.539062 2.25 2.4375 2.25 Z M 2.34375 2.25 ",
"M1.7 -1.7h-0.8c0.3 -0.2 0.6 -0.5 0.6 -0.9c0 -0.6 -0.4 -1 -1 -1c-0.6 0 -1 0.4 -1 1c0 0.4 0.2 0.7 0.6 0.9h-0.8c-0.4 0 -0.7 0.3 -0.7 0.6v1.9c0 0.3 0.3 0.6 0.6 0.6h0.2c0 0 0 0.1 0 0.1v1.9c0 0.3 0.2 0.6 0.3 0.6h1.3c0.2 0 0.3 -0.3 0.3 -0.6v-1.8c0 0 0 -0.1 0 -0.1h0.2c0.3 0 0.6 -0.3 0.6 -0.6v-2c0.2 -0.3 -0.1 -0.6 -0.4 -0.6z"
]
},
"legend": null
},
"color": {
"field": "type",
"type": "nominal",
"legend": null,
"scale": {
"domain": [
"flag", "space", "bomb", "user"
],
"range": [
"rgb(194,81,64)",
"rgb(131,149,91)",
"rgb(93,93,93)",
"rgb(91,131,149)"
]
}
},
"opacity": {"value": 1},
"size": {"value": 30}
}
}
```
Un joven desarrollador del grupo GiGame al conocer el caso se interesa y decide emprender el desarrollo de un juego basado en los diagramas y las anotaciones encontradas. Las reglas completas del juego son:
1. Al empezar cada nivel del juego se presenta un tablero cuadrado con 4 posibles iconos: una bandera, un punto, una bomba y una persona. Solo existe un ícono de bandera y uno de persona por nivel.
2. El jugador (representado por el ícono de la persona) puede moverse en 8 direcciones, a menos que haya una pared: arriba, arriba-derecha, derecha, abajo-derecha, abajo, abajo-izquierda, izquierda y arriba-izquierda.
3. Si el jugador se mueve a un espacio en el que:
* Hay una bomba: entonces pierde y se reinician sus puntos de juego.
* Hay un punto: entonces gana un punto de nivel.
* Hay una bandera: entonces el nivel concluye y se suman sus puntos del nivel al puntaje del juego.
4. Si el jugador llega a la bandera con puntos innecesarios, los pierde, ya que debe usar el camino más corto posible entre su estado inicial y la bandera.
Para probar los niveles del juego te pide que desarrolles un algoritmo el cual lea un mapa de nivel en carácteres de texto y retorne si es un nivel válido y en tal caso indique la mínima cantidad de puntos necesaria para superarlo.
### Entradas
Cada caso de prueba es un nivel de juego. Para cada caso la primera línea contiene un entero $n$ ($1 < n \leq 10^6$) que determina el tamaño del nivel.
Las siguientes $n + 2$ líneas contienen $n + 2$ carácteres que describen el mapa del nivel. Cada carácter puede ser uno de los siguientes 7 carácteres: ```;``` (que representa un muro angular del nivel), ```|``` (que representa un muro lateral del nivel), ```-``` (que representa un muro colateral del nivel), ```*``` (que representa una bomba del nivel), ```.``` (que representa un punto del nivel), ```F``` (que representa la bandera del nivel) e ```i``` (que representa a la persona en el nivel).
Al acabar un caso, debes leer el siguiente caso. De no encontrar un siguiente caso debes finalizar tu algoritmo.
### Salidas
Para cada caso, si no es posible llegar a la bandera debe imprimirse en una línea ```-1```. Por el contrario, si es posible debe imprimirse en una línea la cantidad de puntos $p$ que se sumarán por el nivel, precedido por ```+```.
### Ejemplos
#### Entradas
```
3
;---;
|F*.|
|.*i|
|...|
;---;
4
;----;
|i...|
|.*.*|
|.*F*|
|....|
;----;
3
;---;
|*F*|
|***|
|*i*|
;---;
2
;--;
|F*|
|*i|
;--;
3
;---;
|i.*|
|.*.|
|*.F|
;---;
```
#### Salidas
```
+2
+2
-1
+0
+2
```
### Solución propuesta
Se propone una solución con un recorrido global, una cola, una división en subproblemas para el procesamiento, un mecanismo de memoización y un patrón estrategia para precomputo.
- Recorrido global: una matriz de n^2 en la que se almacenen los valores actuales de las posiciones que se han procesado.
- La cola: almacena las pocisiones que actualmente forman parte de la solución.
- División en subproblemas: cuando se toma la cabeza de la cola se resuelven la cantidad de puntos al moverse desde la posición en la cabeza a todos cada punto en el subproblema. El subproblema más pequeño son las 8 direcciones al rededor de la cabeza.
- Memoización: Al obtener un subproblema compara si ya se ha observado anteriormente, en caso que sí, debe actualizar la matriz de recorrido global y agregar a la cola las posiciones que tenga en memoria para el caso.
- Patrón estrategia: para optimizar la exploración se puede optar por el patrón estrategia con cuatro modos:
- Lectura: Cuando se está leyendo el problema y aun no se ha empezado a llenar la cola.
- Espera: Cuando hay al menos una cabeza en la cola, pero no se ha leido lo suficiente del problema para construir una subestructura procesable.
- Exploración: Cuando hay una cabecera en la cola y datos suficientes para construir una subestructura.
- Punto muerto: Cuando en algún momento hubo una cabeza en la cola, pero ya no hay datos en la cola. Esto es un punto muerto ya que significa que no hay camino que conecte la pocisión de inicio con la final.
La cola debe iniciar cuando se lea un caracter ```i``` o ```F```. Luego la cola puede contener cualquier posición.
### Solución alternativa
A través de Dijkstra simplificado también se puede resolver el problema. Para ello se necesita tener en cuenta que:
- El laberinto se encuentra en área cuadrada de lados $n$, entonces se tienen $n^{2}$ posibles nodos interconectados (en el peor caso, dónde no hay bombas).
- La distancia entre dos nodos interconectados siempre es $1$.
- De lo anterior se puede concluir que la única información relevante a la solución que aportan los nodos son sus conexiones, ya que la distancia es la misma siempre.
- De las dos anteriores se puede notar que las conexiones de un nodo siempre están limitadas a sus 8 posibles vecinos. Esto es importante para la implementación, ya que en Dijkstra se pide que se compare un nodo padre con los demás $n$ nodos para determinar la menor conexion que presenta. En este caso se puede simplificar la búsqueda a los 8 nodos vecinos.
- De lo anterior también se puede deducir algo importante para la implementación, y es que los caminos óptimos cuando se permiten diagonales suelen contenerlas, así que para optimizar también se puede manipular el orden en que se evaluan los vecinos a un nodo para que se evaluen primero los vecinos diagonales.
Con todo esto en cuenta se puede desarrollar una implementación de Dijkstra simplificado que optimice el proceso de búsqueda en la solución.
Otras consideraciones son que los datos se procecen lo antes posible, de poder ser durante la lectura de datos. Para ello se debe tener en cuenta que el punto de inicio de la implementación de Dijkstra debe coincidir con el inicio o con el final del recorrido (no tiene importancia cual).
Ademas, una característica en la lectura del problema es que se puede almacenar en un unico vector de tamaño $3n$, teniendo en cuenta que cada nodo puede conectarse con a lo mucho nodos en la hilera superior, inferior o en su misma hilera a los lados, no se necesita más que un vector $3n$ para actualizar las conexiones.
Sign in with Wallet
Connect another wallet