# TDA | Practica 4 ejercicio 8
## Enunciado
- $8.\star$Se tiene una grilla con $m\times n$ posiciones, cada una de las cuales tiene un número entero en $[0,k)$, para un $k\in\mathbb{N}$ dado. Dado un valor objetivo $w\in\mathbb{N}$ y una posición inicial $(x_1,y_1)$, que tiene un valor inicial $v_1$, queremos determinar la mínima cantidad de movimientos horizontales y verticales que transformen $v_1$ en $w$, teniendo en cuenta que el $i$esimo movimiento transforma a $v_i$ por $v_i+ 1= ( v_i+ z)$ mód $k$, donde $z$ es el valor que se encuentra en la casilla de destino del movimiento.
- Por ejemplo, para la siguiente grilla y $k=10$,se puede transformar $v_1=1$ en $w=0$ con tres movimientos $1\to6\to4\to9$, aunque la solución óptima es vía el camino $1\to3\to6.$
- Modelar este problema como un problema de grafos que se resuelva usando BFS en $O(k \times m \times n)$ tiempo.
## Resolución
- $k$ es el máximo valor que puede tomar cualquier número en la grilla más uno.
- Define el rango de valores desde $0$ hasta $k-1$.
- cuando se opera sobre algún valor $v_i$, el resultado se calcula mediante aritmetica modular con módulo $k$.
- Para $v_i \Rightarrow \ w : \ v_{i+1} = (v_i + z)$ mód $k$
- $z$ es el valor de la casilla destino.
- Si te moves a una casilla con un valor especifico $z$, sumo $z$ al valor actual $v_i$ y aplico módulo $k$ para asegurarme que esté en rango.
- Entonces hay que seleccoinar los movimientes que desde $v_1$, me permiten sumar $w$ con BFS.
- 
- Voy a armar una estructura que sea algo como:
```pseudocode
struct estado {
coordenadas (x,y),
v : valorActual
}
```
#
```pseudocode
mientras que la cola no esté vacía:
- extraé el primer elemento de la cola
- si v_i == w entonces ya encontré la solución más optima
- Hacer todo el calculo v_i = (v+z) mod k etc etc
- si no fue visitado, encolalo
- Andá acumulando la respuesta
```
#
### Código en python mediante una clase
#### Tengo mis dudas sobre la complejidad asintotica del algoritmo, preguntar en clase.
```python
from queue import Queue
class Estado:
def __init__(self, x, y, valor):
self.x = x
self.y = y
self.valor = valor
def bfs(grilla, inicio_x, inicio_y, valor_inicial, valor_objetivo, k):
# Direcciones para los movimientos: arriba, abajo, izquierda, derecha
direcciones = [(-1, 0), (1, 0), (0, -1), (0, 1)]
m = len(grilla)
n = len(grilla[0])
# Crear una cola para BFS
cola = Queue()
estado_inicial = Estado(inicio_x, inicio_y, valor_inicial)
cola.put(estado_inicial)
# Conjunto para mantener registro de los estados visitados
visitados = set()
visitados.add(estado_inicial)
# Número de movimientos
movimientos = 0
# En el peor caso visitaremos todas las celdas de la grilla O(mn)
while not cola.empty():
tamano_nivel = cola.qsize() # Tamaño del nivel actual
# Explorar todos los nodos en el nivel actual
for _ in range(tamano_nivel):
estado_actual = cola.get() # Extraé el estado actual
# Verificar si hemos alcanzado el objetivo
if estado_actual.valor == valor_objetivo:
return movimientos
# Explorar todos los movimientos posibles
for dx, dy in direcciones:
nx, ny = estado_actual.x + dx, estado_actual.y + dy
if 0 <= nx < m and 0 <= ny < n: # Asegurar que estamos dentro de los límites de la grilla
# v_i + z mod k
nuevo_valor = (estado_actual.valor + grilla[nx][ny]) % k
nuevo_estado = Estado(nx, ny, nuevo_valor)
# Si el nuevo estado no ha sido visitado, lo agregamos a la cola
if nuevo_estado not in visitados:
cola.put(nuevo_estado)
visitados.add(nuevo_estado)
# Incrementar el número de movimientos después de explorar un nivel completo
movimientos += 1
# Si salimos del ciclo sin haber encontrado el objetivo
return -1
```
#
Para testear:
```python
def main():
# Suponer una grilla definida, valores de inicio y objetivo
grilla = [
[1, 3, 6],
[6, 7, 4],
[4, 9, -3]
]
inicio_x, inicio_y = 0, 0 # Posición inicial
valor_inicial = 1 # Valor inicial en la posición (0, 0)
valor_objetivo = 0 # Valor que queremos alcanzar
k = 10 # Módulo
# Llamada a la función BFS
resultado = bfs(grilla, inicio_x, inicio_y, valor_inicial, valor_objetivo, k)
print("Número mínimo de movimientos necesarios:", resultado)
if __name__ == "__main__":
main()
```