Problem Source: SPOJ Problem Set (classical): 4235. Wandering Queen
Basically you are given a grid with a start and end point along with some obstacles. You have to reach end point using smallest number of standard chess queen moves.
The first idea that pops into mind is using BFS, along with states for 8 direction. In this case, the complexity is around 8 * 256 * 1000 * 1000. Anyone who is a bit familiar with SPOJ engine, knows that, this solution will definitely get a "Time Limit Exceed" verdict.
The catch is, it doesn't matter for a standard chess queen from which direction you reach a particular cell in terms of cost. A queen moves toward 8 directions as long as nothing is blocking her paths and the cost remains the same. So, whenever you reach a cell, you will want to traverse all of the 8 possible directions from that cell. If you maintain the previous direction, the cost will not change, and if you change direction, the cost will be increased by 1. Fortunately, we can maintain the BFS property without keeping extra states for direction simply by adding a parallel flag array and modifying how we choose the next cell.
Although there are 8 possible directions, we have only 2 different scenarios, namely: whether we want to change direction or not. Instead of keeping states for direction changes, we will visit all cells in a particular direction from a specific cell before traversing from other cells and pushing them into a queue as usual. Following this, we can visit all the reachable cells from a particular cell in a single move. During this process, we will store the bit-masked flags for direction in a parallel array. Now, when we meet a new cell, there are four possible scenarios.
1 ⇒ The cell is out of the grid or contain an 'X', simply stop moving in that direction anymore.
2 ⇒ The flag value for this cell already has the bit for current direction set to 1. It means, going in this direction doesn't do anything helpful anymore.
3 ⇒ The flag value for this cell doesn't contain bit for current direction, but it has been visited form different direction earlier. We just skip this cell and continue with the direction. Note: This step is important to understand. Because at first this may seem like, we can just stop here as the cell is already in the queue and will be traversed later. But thinking carefully, you will find out that, your current move will definitely have a lower or equal cost than the current cell which resides in the queue will have (obvious BFS property). So, we may still need to update the rest of the cells following the direction. Although we skip this cell, we update its flag value to mark the direction from which it was visited. See sample case 2, that explains the necessity of this step.
4 ⇒ New cell, we visit it, do regular BFS stuffs like updating cost, pushing into queue, and additionally, we mark the direction from which it was visited in the flag array.
Oh, and ofcourse, flag for the start cell should have all the bits set. Now, we visit each cell at most 8 times for each direction, but we push each cell only once into the queue. Thus, we are able to remove the 256 different bitmasked states, and the solution is more likely to pass the time limit.
Following this procedure, I got accepted in 2.56 with STL queue, and no IO optimization. I am having a feeling that, this problem can be solved more efficiently. So, don't forget to share your idea on this problem.
