BFS is our friend. We keep a queue of pairs where the first element will show us the coordinate of the current node ( the coordinate is a single number) and the number of rolls we made so far. We also should keep a boolean array MARK where MARK[I] shows whether we have already visited the node I or not. Initially our queue has one element, the coordinate 1 and a distance 0. After that for all the front elements of the queue, we take it out, pop it away, then we look over all the coordinates which are 1,2,3,4,5, or 6 steps away from our current coordinate and if they are not visited then we mark them as visited and push them into the queue. We also need to take care of the snakes and ladders. We can keep an array PATH, where PATH[I] shows us the number of a cell which we would have to travel if we somehow landed on the cell I. Check the source code for a better understanding.
No comments:
Post a Comment