Count right/down paths through a grid while avoiding shelves
A warehouse robot starts at the loading dock in the top-left corner of a floor map and must deliver a package to the packing station in the bottom-right corner. To keep traffic flowing in one direction, it may only move right or down, one cell at a time, and it cannot drive through shelves.
Implement countRobotRoutes(grid). It returns how many different routes the robot can take.
countRobotRoutes(grid) // => number
grid is an array of strings. Each string is one row, and every row has the same length. grid[r][c] is the cell in row r, column c.'.' is open floor and '#' is a shelf.grid[0][0] and ends at the bottom-right cell. Every cell on the route, including both ends, must be open.0.Number.MAX_SAFE_INTEGER.countRobotRoutes([
'...',
'...',
]);
// => 3 (right-right-down, right-down-right, down-right-right)
countRobotRoutes([
'...',
'.#.',
'...',
]);
// => 2 (around the shelf on either side)
countRobotRoutes([
'....',
'.#..',
'...#',
'#...',
]);
// => 3
countRobotRoutes(['.#', '#.']);
// => 0
countRobotRoutes(['.']);
// => 1
Trying every route takes exponential time. Aim for O(rows × cols) time. Can you use only O(cols) extra space?