Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa Última revisión Ambos lados, revisión siguiente | ||
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 04:34] sebach [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. | 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: | 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", los vectores quedarían: | ||
<code cpp> | <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> | </code> | ||