232. Paths Through a Maze
Challenge1000 ms256 MBSolved by 0%
A grid of m rows and n columns. 0 is an open cell and 1 is a wall.
Starting at the top-left, moving only right or down, print how many paths reach
the bottom-right.
This is problem 223 with obstacles, and the obstacles change one thing: a blocked cell contributes nothing, whatever leads into it.
Check both ends before anything else. If the start or the finish is a wall the answer is 0, and a solution that assumes the start is open will read a cell it should not.
Constraints - `1 ≤ m ≤ 15` - `1 ≤ n ≤ 15`
Input
The first line contains two integers m and n.
The next m lines each contain n characters, each 0 or 1.
Output
Print one integer, the number of paths from the top-left to the bottom-right.
Input3 3
000
000
000
Output6
Notehas no walls, so it matches the open-grid count
Input3 3
000
010
000
Output2
Notehas one wall in the centre, which removes four of the six paths
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.