Robot Turtles

Explicación

Podemos usar Dijkstra, llevando la cuenta de la longitud actual del programa ( $\texttt{dist}$ ), la dirección a la que mira la tortuga ( $\texttt{dir}$ ) y los movimientos que ya ha hecho para llegar a su ubicación actual ( $\texttt{moves}$ ). Si hay un castillo de hielo frente a la tortuga, solo debería derretirse si la tortuga se va a mover allí de inmediato. Si la tortuga no se mueve a la casilla de inmediato, entonces o bien:

volverá a la casilla más tarde, en cuyo caso la tortuga ha desperdiciado movimientos antes de volver.
nunca se moverá a la casilla, en cuyo caso la tortuga desperdició un movimiento derritiendo el castillo de hielo. Así, solo necesitamos derretir castillos de hielo si la tortuga avanza de inmediato después.

En cada ubicación, la tortuga puede:

avanzar si hay una casilla vacía.
derretir un castillo de hielo y luego avanzar si hay un castillo de hielo.
girar. A medida que hacemos movimientos, agregamos las instrucciones al string $\texttt{moves}$ . Una vez que llegamos al diamante, podemos imprimir $\texttt{moves}$ .

Implementación

Complejidad temporal: $\mathcal{O}(N^2\log N^2)$ , donde $N$ es la longitud del lado del tablero.

C++


#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
 
struct State {
	// direcciones: 0 es arriba, 1 es derecha, 2 es abajo, 3 es izquierda
	int dist, i, j, dir;
	string moves;
	bool operator>(const State &a) const { return dist > a.dist; }
};
 
bool ingrid(int a, int b) { return a >= 0 && a < 8 && b >= 0 && b < 8; }
 
int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
 
int main() {
	string grid[8];
	for (int i = 0; i < 8; i++) { cin >> grid[i]; }
	int dist[4][8][8]{};  // dir, i, j
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 8; j++) {
			for (int k = 0; k < 8; k++) { dist[i][j][k] = 1e9; }
		}
	}
	dist[1][7][0] = 0;
	priority_queue<State, vector<State>, greater<State>> pq;
	pq.push({0, 7, 0, 1, ""});
 
	// usamos Dijkstra para hallar el camino más corto al diamante
	while (!pq.empty()) {
		State cur = pq.top();
		pq.pop();
		if (cur.dist != dist[cur.dir][cur.i][cur.j]) { continue; }
		if (grid[cur.i][cur.j] == 'D') {
			cout << cur.moves << endl;
			return 0;
		}
 
		// avanzar
		int newi = cur.i + di[cur.dir], newj = cur.j + dj[cur.dir];
		if (ingrid(newi, newj) &&
		    (grid[newi][newj] == '.' || grid[newi][newj] == 'D') &&
		    dist[cur.dir][cur.i][cur.j] + 1 < dist[cur.dir][newi][newj]) {
			dist[cur.dir][newi][newj] = dist[cur.dir][cur.i][cur.j] + 1;
			pq.push({dist[cur.dir][newi][newj], newi, newj, cur.dir, cur.moves + "F"});
		}
 
		// derretir castillo de hielo y avanzar
		if (ingrid(newi, newj) && grid[newi][newj] == 'I' &&
		    dist[cur.dir][cur.i][cur.j] + 2 < dist[cur.dir][newi][newj]) {
			dist[cur.dir][newi][newj] = dist[cur.dir][cur.i][cur.j] + 2;
			pq.push({dist[cur.dir][newi][newj], newi, newj, cur.dir, cur.moves + "XF"});
		}
 
		// girar a la izquierda o a la derecha
		for (int turn : {-1, 1}) {
			int newdir = (cur.dir + turn + 4) % 4;
			string newmove = (turn == -1 ? "L" : "R");
			if (dist[cur.dir][cur.i][cur.j] + 1 < dist[newdir][cur.i][cur.j]) {
				dist[newdir][cur.i][cur.j] = dist[cur.dir][cur.i][cur.j] + 1;
				pq.push({dist[newdir][cur.i][cur.j], cur.i, cur.j, newdir,
				         cur.moves + newmove});
			}
		}
	}
 
	cout << "no solution" << endl;
}