Hi. I am new to codechef. I want to code the problem named " A puzzle game". It is the first problem in beginner level. But I cant understand how to approach. Please anyone give me a hint so that I can approach the problem.
Okay this problem is a little bit hard for beginners so don’t worry if you don’t understand I will give hints one by one read one by one and as soon as you get something that you have missed go back to the problem to solve it if even then you can’t solve then read further hints
Click to view
you see the maximum sum can be only 17 that is 9+8 so you can precalculate for which values you can swap that are 2,3,5,7,11,13 and 17
Click to view
if you can get from the given state to the initial state you can also get from initial state to the given state
Click to view
You can precalculate all the states that can be reached from the initial state that is 123456789 by doing a bfs from 123456789 and making the edges to those states which can be achieved by swapping two valid numbers(sum of which is 2)from the current state and store them in a array. In case you doesn’t know what bfs is study that first.
https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/
Click to view
Now you have stored all the states that can achieved from initial state but while precalculating also store the distance from initial state that is the number of steps to reach to the state the distance from the state 123456789, for the state 123456789 distance would be 0.
Click to view
The distance would be the level of the current state in the bfs as bfs gives the shortest path in terms of number of edges
Click to view
now just get the input and see whether this state is achievable or not. if it is print the distance of the state from the initial state else print -1
I wonder how did you save the step for each state.
I stored states in a truct like this
struct cube_t{
int X11 , X12 , X13;
int X21 , X22 , X23;
int X31 , X32 , X33;
bool operator ==(const cube_t& cb) const {}
bool operator <(const cube_t& cb) const{}
void operator =(cube_t& cb) const{}
};
and i tried to store step with a map
map<cube_t,int> m_Cube;
but that was not work correctly, the map cannot compare correctly bettween 2 the same cube_t and i have to changed to this
map<long long int,int> m_Cube;
and it work correctly.