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
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution