A floor-scrubbing robot drives on a grid map, a list of strings grid where grid[row][col] is '#' for an obstacle and '.' for floor (row 0 at the top). It always faces one of four headings: "N" (towards row 0), "E" (towards larger columns), "S" and "W". It can do three things:
- drive one cell straight ahead onto a floor cell inside the map, taking
driveseconds; - turn left or turn right by 90 degrees on the spot, taking
turnseconds (a half turn is two of these).
A planner that counts only cells would hand it a zigzag; this one counts seconds. The robot starts on start facing facing; it has arrived as soon as it stands on goal, whatever its heading.
Write fastest_arrival(grid, start, facing, goal, drive, turn) that returns the smallest number of seconds needed, or None if the goal cannot be reached.
Examples
Input: grid = ["....#.",
"..#...",
".#..#.",
"...#.."], start = (3, 0), facing = "N", goal = (0, 5), drive = 1.0, turn = 0.5
Output: 11.0
Explanation: the shortest route has 8 moves, staircasing up through the middle; with
the turn at the start it needs 6 turns: 8 + 6 * 0.5 = 11.
Input: the same, with turn = 2.0
Output: 18.0
Explanation: now it pays to drive 10 cells (up column 0, along row 0, down one, across
and up into the goal) with only 4 turns: 10 + 4 * 2 = 18, while the staircase costs 20.
Input: grid = ["..."], start = (0, 0), facing = "W", goal = (0, 2), drive = 1.0, turn = 3.0
Output: 8.0
Explanation: two turns to face east, then two cells.
Constraints
- all rows have the same length;
startis a floor cell; floats are compared with a tolerance of1e-6
Goals
- Search over states that hold both the cell and the robot's heading
- Give turning in place its own cost, next to driving
- See a longer route win because it turns less