> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-1/e-dacey-the-dice.md).

# E: Dacey the Dice

https\://open.kattis.com/problems/daceydice

* This is a standard [Breadth-First-Search](https://cp-algorithms.com/graph/breadth-first-search.html)/[Depth-First-Search](https://cp-algorithms.com/graph/depth-first-search.html) problem. 
* The **main challenge is keeping track of the orientation of the dice** as it rolls along.
* The key observation (as hinted in the question) is that any two adjacent faces uniquely determine the rest of the dice. So, it is **sufficient** to keep track of, say, the top and right face alone.
* This way, our search space (and hence `visited` tables used in search) are of size `n*n*6*6 (x-coordinate, y-coordinate, top-face, right-face).`
* If the start location is `(x1,y1)` and ending location is `(x2,y2)`, we would like to start our search at `(x1,y1,1,2)` and claim we found a path any time we hit a location of the form `(x2,y2,2,*)`. Note that we end when we reach the destination with `5` at the bottom: this corresponds to having `2` at the top; the right face does not matter.

{% hint style="info" %}
Be careful when generating the neighbors of any given node. In particular, make sure to correctly change the top and right face according to the direction you are moving in. 

*Example:* Suppose your top face and right face are currently `1` and `2` respectively. Now, if you roll up, your top face becomes `3` and the right face remains `2`.
{% endhint %}