OIA-Wiki

Algo muy común es querer llegar desde un punto a otro, pero teniendo en cuenta alguna otra variable, o más de una. Por ejemplo, queremos ir en bicicleta de un punto a otro pero doblando (cambiando de dirección) la menor cantidad de veces; o ir a buscar un tesoro en un tablero con monstruos, teniendo una cierta cantidad de hechizos para dormir una cierta cantidad de monstruos en el camino.

En estos casos, no nos importa únicamente en qué casilla estamos, sino el estado de la otra variable. Y esto va a depender del caso: en el primer caso, nos importa saber en qué dirección estamos yendo al llegar a una casilla, ya que al salir de ella tenemos que saber si contar una doblada o no; en el segundo caso, nos va a importar cuántos hechizos nos quedan, para saber si podemos ir adonde hay un monstruo y dormirlo o no.

Concentrémonos en el último ejemplo, que es muy parecido al problema tesoro del Juez.

Queremos calcular la menor cantidad de movimientos que son necesarios para llegar desde la casilla inicial hasta el tesoro, donde lo permitido es ir a un vecino si está vacío o si hay un monstruo y nos quedan flechas, aunque deberemos gastar una. Ahora, obviamente no nos sirve guardar para cada casilla la menor cantidad de movimientos hasta ella nada más, porque no sabemos si desde ahí no nos vamos a poder mover hacia casillas con monstruos, o quizás nos conviene llegar a una casilla en más pasos que el mínimo pero guardarnos una flecha para después.

Entonces, así como antes en un bfs “común” un estado era la casilla en la que estábamos, ahora será la casilla junto con la cantidad de flechas que tenemos en ese momento.

Hay muchas maneras de hacer esto, la que vamos a mencionar acá usa struct, y también usa la manera de moverse a vecinos mencionada acá.

Vamos a hacer entonces un struct “estado”, que también podría llamarse “coordenada”, o “casillaConInformacion”, o lo que sea, donde guardaremos la posición de la casilla y la cantidad de flechas, como mencionamos. Y vamos a tener un vector de 3 dimensiones, $vector<vector<vector<int> > > pasos$, que en $pasos[x][y][f]$ nos diga la menor cantidad de pasos necesarios para llegar hasta la casilla $(x,y)$ con $f$ flechas. Cabe destacar que si podemos llegar a la casilla $(x,y)$ con $f$ flechas de varias maneras, querremos la más corta, porque no hay otras variables que nos afecten. Si además de esto, quisiéramos “girar” como mencionamos al principio la menor cantidad de veces, habría que agregar esta variable a nuestra struct, y una dimensión más al vector “pasos”.

Cómo encontrar la solución: Al final, vamos a tener para cada casilla, para cada cantidad de flechas, la menor cantidad de pasos de llegar desde el estado inicial hasta ese estado. Como queremos la menor cantidad de pasos necesarios para llegar al tesoro sin importar la cantidad de flechas que nos queden, entonces al final, simplement hacemos un for para iterar sobre la cantidad de flechas finales, y agarramos la menor cantidad de pasos entre todas esas posibilidades.

Y para reconstruir el camino sabiendo el estado en el que terminamos, probamos ir a los vecinos, y si la menor cantidad de pasos para llegar al estado vecino es $1$ menos que para el estado actual, quiere decir que venimos de ahí.

Dejo un código basado fuertemente en una solución enviada al juez, pero usando struct. Pueden ver otros códigos del juez para sacar otras ideas, pero les recomiendo elegir la manera que les sea más sencilla y “adaptable” (para mí es esta, con struct) y quedarse con ella para todos estos problemas.

tesoro.cpp

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i,n) for(int i=0;i<(int)(n);i++)
 
vector< vector<char> > tablero(125, vector<char>(125));
 
vector< vector< vector<int> > > pasos(125, vector< vector<int> >(125, vector<int>(125, -1)));
 
// para ver a los vecinos
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
 
 
struct estado{
	int x, y, f;
	estado(int nx, int ny, int nf): x(nx), y(ny), f(nf) {}
};
 
bool estaAdentro(int x, int y, int M, int N){
	return 0 <= x && x < M && 0 <= y && y < N;
}
 
int main(){
    ifstream cin("tesoro.in");
    ofstream cout("tesoro.out");
    int M,N,F;
    cin >> M >> N >> F;
    int tX,tY;
    forn(i,M){
		forn(j,N){
			cin >> tablero[i][j];
			if (tablero[i][j] == 'T'){
				tX = i;
				tY = j;
			}
		}
    }
 
    int cfp = 0;
    int startF = F - (tablero[0][0] == 'W');
    if (tablero[0][0] != 'P' && startF >= 0){
        queue<estado> q;
        pasos[0][0][startF] = 0;
        q.push(estado(0, 0, startF));
        while (!q.empty()){
            estado actual = q.front();
            q.pop();
            int x = actual.x;
            int y = actual.y;
            int f = actual.f;
            // Ver vecinos
            forn(k,4){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (estaAdentro(nx, ny, M, N)){
                    if (tablero[nx][ny] == 'W' && f > 0 && pasos[nx][ny][f-1] == -1){
                        pasos[nx][ny][f-1] = pasos[x][y][f]+1;
                        q.push(estado(nx, ny, f-1));
                    }
                    if ((tablero[nx][ny] == 'V' || tablero[nx][ny] == 'T') && pasos[nx][ny][f] == -1){
                        pasos[nx][ny][f] = pasos[x][y][f]+1;
                        q.push(estado(nx, ny, f));
                    }
                }
            }
 
        }
 
        int res = 1000000000;
        for (int cf = 0; cf <= F; cf++){
			if (pasos[tX][tY][cf] != -1 && pasos[tX][tY][cf] < res){
				res = pasos[tX][tY][cf];
				cfp = cf;
			}
		}
    }
    if (pasos[tX][tY][cfp] == -1){
        cout << "imposible" << endl;
    }else{    
        cout << pasos[tX][tY][cfp] + 1 << endl;
        vector< pair<int,int> > v;
        int x = tX, y = tY, f = cfp;
        while ((x != 0 || y != 0)){
            v.push_back(make_pair(x, y));
            forn(k,4){
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (estaAdentro(nx, ny, M, N)){
                    int costeFlecha = tablero[x][y] == 'W';
                    if (pasos[nx][ny][f+costeFlecha] + 1 == pasos[x][y][f]){
                        x = nx;
                        y = ny;
                        f = f + costeFlecha;
                        break;
                    }
                }
            }
        }
        v.push_back(make_pair(0,0));
        forn(i, v.size()){
			pair<int,int> voy = v[v.size()-i-1]; // lo guardamos de atras para adelante, lo imprimimos en el orden del recorrido.
			cout<<"("<<voy.first<<","<<voy.second<<")"<<endl;
		}
    }
    return 0;
}

Protesta

Indiana

Ajedrez, un poquito más complicado