A robot vacuum's companion app plans a route across a room drawn as a grid of strings: "S" is the robot, "G" is the dock, "." is open floor, and "#" is furniture. The robot moves up, down, left, or right, one cell per step.
The planner uses A* search with the Manhattan distance (|row difference| + |column difference|) to the dock as its guess of the remaining steps. Write routeLength(room) that returns the number of steps in the route it finds, which is the fewest steps to the dock, or -1 if the dock can't be reached.
Input: room = ["S..#",".#..","...G"] Output: 5
Going down twice and then right three times reaches the dock in 5 steps, which equals the Manhattan distance, so nothing can be shorter.
Input: room = ["S#G"] Output: -1
Furniture blocks the only way.
1 <= room.length, room[i].length <= 200"S" and one "G".Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #468 Robot Vacuum Route With A*. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.