COSC 3331 Northeast Grid Path

Problem:

Consider a network of streets laid out in a rectangular grid, there is no negative value, the smallest point is (0,0). For example see image.

In a northeast path from one point in the grid to another, one may walk ONLY to the north (top) and to the east (right). For example, there are four northeast paths from A to B in the preceding grid: see image.

Write a program that uses one or two recursive functions to

1) count the number of northeast paths from one point to another (user could input the values) in a rectangular grid, and
2) print out all the paths like:

For example, there are 4 paths from (0,1) to (3,2)
(0,1) (0,2) (1,2) (2,2) (3,2)
(0,1) (1,1) (1,2) (2,2) (3,2)
(0,1) (1,1) (2,1) (2,2) (3,2)
(0,1) (1,1) (2,1) (3,1) (3,2)

Hint:

There are mainly two parts you need to design for this project

• The total number of the paths, you should use a recursive method to calculate that.
• To print each individual path, you should have another recursive method design to do this part, and one approach is to have an argument as string to record every step and finally to print it.