E: Dacey the Dice

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

• This is a standard Breadth-First-Search/Depth-First-Search 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.

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.