Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero [2017/12/27 13:18]
sebach [Problemas para practicar]
+++ algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero [2018/01/07 05:02] (actual)
guty [Ir a casillas vecinas]
@@ Línea 1: / Línea 1: @@
-===== Si en vez de ir a casillas adyacentes, hay distintos movimientos? =====
+===== Ir a casillas vecinas =====
+En muchos problemas, estamos en un tablero, y tenemos permitido movernos a casillas vecinas (a veces pueden estar bloqueadas y no se podrá entrar). Es decir, lo importante es que desde cualquier casilla, tenemos siempre **las mismas posibilidades de movimiento**: arriba, abajo, izquierda, derecha.
+Habrá casos particulares de cuando estamos en un borde por ejemplo, no podremos salirnos del tablero.
+Una primera manera de ir a las casillas vecinas de $(i, j)$, es, a mano, ver de ir a $(i+1, j)$, $(i-1, j)$, $(i, j+1)$, $(i, j-1)$.
+En este caso es sencillo porque hay sólo cuatro posibles movimientos. Si en cambio pudiéramos movernos a una casilla con la que comparte un punto (las casillas con las que comparte una esquina), ya habría $8$ lugares a los cuales moverse.
+Aunque haya pocas casillas vecinas, hacer cada movimiento por separado es más propenso a errores: a veces terminamos copiando y pegando código para repetir el accionar en cada vecino; ponemos un $+1$ en vez de un $-1$ y dejamos vecinos sin ver.
+Pero además de los posibles errores, esta manera siempre nos hace escribir varias veces lo mismo.
+¿Qué pasaba cuando teníamos menos conocimiento y hacíamos cosas más básicas, cuando queríamos hacer varias veces lo mismo? **FOR!**
+La clave es, en un for, "movernos" por todos los vecinos. ¿Cómo? No es tan simple como un $for(vecino : vecinos)$ porque no tenemos una lista de vecinos. (Esto tiene que ver con tener un grafo de manera implícita, pueden leer un poco [[algoritmos-oia/grafos#representacion_en_la_computadora|acá]].)
+Para hacer esto, podemos tener dos vectorcitos, $dx$ y $dy$, que en la posición $i$, los vectores nos digan que para ir al i-ésimo vecino debo moverme $dx[i]$ en la dirección $x$, y $dy[i]$ en la dirección $y$.
+Para ir a las casillas vecinas como dijimos, tendríamos ''vector<int> dx = {1, -1, 0, 0};'' y ''vector<int> dy = {0, 0, 1, -1};''
+** Y qué pasa si en vez de que las casillas vecinas sean las adyacentes, son otras? **
 Algo que es muy común es tener distintos tipos de movimientos más allá de ir a casillas adyacentes en un tablero. El ejemplo más típico es el movimiento del caballo en el ajedrez.
@@ Línea 5: / Línea 25: @@
 Un caballo puede moverse a otra casilla si el "camino" de casillas adyacentes para ir de una a la otra forma una L, donde el palito largo de la L tiene $3$ casillas y el corto tiene $2$, como se ve en la siguiente figura:
-{{ :algoritmos-oia:grafos:bfs:caballo-movimientos.jpeg?400 |}}
+{{ :algoritmos-oia:grafos:bfs:caballo-movimientos.jpeg?200 |}}
-Entonces, lo que vamos a hacer, es guardar en dos vectores, cuánto nos movemos en la dirección vertical y cuánto en la vertical, respectivamente.
+Entonces, lo que vamos a hacer, es usar la misma idea de los vectores $dx$ y $dy$, sólo que cambiando los elementos.
-Es decir, vamos a tener vectores $dx$ y $dy$ que en la posición $i$-ésima guarden cuántos nos movemos en $x$ y cuánto en $y$, respectivamente (en general, el eje $x$ será el vertical, el de la primera coordenada en un vector de vectores).
+Para simular las movidas desde la posición $(a, b)$, haremos un for para cada movida $i$ e iremos a la posición $(a+dx[i], b+dy[i])$ del tablero, siempre y cuando no nos hayamos ido del límite del tablero.
-Y para simular las movidas desde la posición $(a, b)$, haremos un for para cada movida $i$ e iremos a la posición $(a+dx[i], b+dy[i])$ del tablero, siempre y cuando no nos hayamos ido del límite del tablero.
-Para el movimiento mencionado del caballo, empezando por el de "arriba a la derecha", los vectores quedarían:
+Para el movimiento mencionado del caballo, empezando por el de "arriba a la derecha" y siguiendo en sentido horario, los vectores quedarían:
 <code cpp>
-vector<int> dx = {-2, -1, 1, 2, 2, 1, -1, -2}
+// incrementar en x significa ir a una fila mas abajo, incrementar y significa ir a una columna mas a la derecha
-vector<int> dy = {1, 2, 2, 1, -1, -2, -2, -1}
+vector<int> dx = {-2, -1, 1, 2,  2,  1, -1, -2};
+vector<int> dy = { 1,  2, 2, 1, -1, -2, -2, -1};
 </code>

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página