Official Analysis

Explanation

We can use Dijkstra's, keeping track of the current length of the program ($\texttt{dist}$), the direction the turtle faces ($\texttt{dir}$) and the moves it has already made to reach its current location ($\texttt{moves}$). If there is an ice castle in front of the turtle, it should only be melted if the turtle will move there immediately. If the turtle doesn't move onto the square immediately, then it will either:

• return to the square later, in which case the turtle has wasted moves before returning.
• never move onto the square, in which case the turtle wasted a move melting the ice castle.

So, we only need to melt ice castles if the turtle moves forward immediately after.

At each location, the turtle can:

• move forward if there is an empty square.
• melt an ice castle and then move forward if there is an ice castle.
• turn.

As we make moves, we add the instructions to the string $\texttt{moves}$. Once we reach the diamond, we can print out the $\texttt{moves}$.

Implementation

Time Complexity: $\mathcal{O}(N^2\log N^2)$, where $N$ is the side length of the board.

Copy
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

struct State {
	// directions: 0 is up, 1 is right, 2 is down, 3 is left
	int dist, i, j, dir;
	string moves;