Question :
Find the number of different shortest paths from point A to point B in a city with perfectly horizontal streets and vertical avenues as shown in Figure below. No path can cross the fenced off area shown in grey in the figure.
Solution :
The answer is 17 paths.
The easiest way to get it is to apply dynamic programming — one of the algorithm design strategies discussed in the first tutorial. This approach finds the number of shortest paths from A to every intersection in the grid outside the fenced-off area (see Figure below). Starting with the assignment of 1 to intersection A, these numbers can be computed row by row and left to right within each row. If an intersection has both the left and upper neighbors, its number is computed as the sum of the neighboring numbers; if an intersection has just one of such neighbors, it gets the same number as that of the neighbor.
