Fewest turns
A courier robot drives over a grid plan of a city. It drives straight fast, but at every turn it stops, turns on the spot and accelerates again. So it needs not the shortest route but the route with the fewest turns, even if it is longer.
One of the tests is the centre of Almaty drawn on graph paper: the streets from OpenStreetMap are rotated by the angle of the city grid, a cell is 20 metres, the start is at Republic Square and the finish at the Green Bazaar.
Input
The first line holds the numbers n and m (1 ≤ n, m ≤ 400). Then n lines of m characters: . is a free cell, # a wall, S the start, F the finish (both cells are free, and the start and finish are different). In one move the robot goes to a neighbouring free cell across a side. A turn is a change of direction between two consecutive moves; the first move can be made in any direction for free.
Output
The smallest number of turns on a path from S to F, or -1 if the finish cannot be reached.
Examples
Example 1
7 10 S......... .########. ..#######. #..######. ##..#####. ###..####. ####....F.
2
Example 2
3 5 S..#. .#.#. ...#F
-1
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Find the shortest path by breadth-first search and count the turns on it. Compare with the answer to the first sample.
2Hint 2
To know whether the next move will be a turn, it is not enough to know which cell the robot is in. What else do you need to remember?
3Hint 3
In a graph whose vertex is a pair “cell, direction”, the edges have only two weights: 0 and 1. An ordinary queue no longer works. What about a deque?
4The idea
The robot's state is a cell and the direction it faces. From a state there are two kinds of transitions: drive forward into the neighbouring cell (0 turns) and turn on the spot left or right (1 turn). You need a shortest path in a graph with weights 0 and 1, and there is a trick simpler than Dijkstra for it, 0-1 BFS: in a deque, a vertex reached along an edge of weight 0 is put at the front, and along an edge of weight 1 at the back.
5Walkthrough
Why the deque works. In an ordinary breadth-first search the queue holds vertices of at most two neighbouring layers: k at the head, k + 1 at the tail. Here it is the same: an edge of weight 1 adds a vertex of layer k + 1 at the tail, while an edge of weight 0 gives a vertex of the same layer k, and its place is at the head, before all the k + 1. The deque stays sorted, and vertices are taken in non-decreasing order of distance, exactly what Dijkstra's heap does, only without the logarithm.
The start is four states (S, up), (S, right), (S, down), (S, left) with zero turns: the first direction is free. The answer is the distance of the first state with cell F taken from the deque. A 180° about-turn is never needed: two turns in a row on the spot achieve nothing. The reference surrounds the plan with a frame of walls so as not to check for going over the edge.
Why the first hint does not work: in the first sample the shortest path is a staircase of fourteen moves with nine turns. Going round the edge is two moves longer, with two turns.
5+Solution
6Complexity
There are 4nm states, three transitions from each, and each gets into the deque at most twice: O(nm). Dijkstra with a heap is correct too, but slower by a log factor; in Python on a 400 × 400 plan that is noticeable.
7Common mistakes
- The shortest path, then counting turns. A short path can wind about: this is
wrong.py, and the first sample already catches it. - A distance per cell instead of per pair. If you store one number per cell, a path that reached the cell with the same number of turns but facing the wrong way overwrites a better one.
- An ordinary queue for edges 0 and 1. A vertex found along a zero edge at the tail of the queue will be processed after vertices with a larger distance, and the answer will be spoiled.
- Paying for the first move. The initial direction is chosen for free, so there are four starting states.