Woburn Challenge 1996

Problem 5: Plentiful Paths

Given is an M by N grid and on each square of the grid there may or may not be an apple on it. Let A be the bottom left square and B be the upper right square of the grid. Find the path from A to B (shown below) going up and right only that passes through the most number of squares with apples in them. For this path output the number of apples on it.

For example, here is a 4 by 4 grid:

    .a.a <-B
    ..aa
    a.a.
A-> ....

Each square can have at most one apple (this includes squares A and B).

Input

Your program should read in the size of the grid, M N, where 1 ≤ M, N ≤ 100. The locations of the apples where A is at (1, 1) and B is at (M, N). Inputs will end with 0 0 and have the same format as the one below. In our example, the input would be

4 4
2 1
2 3
3 3
3 4
4 2
4 4
0 0

Output

Give the number of apples on the path with the most number of them. In this case

5

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

so, m is the number of rows and n is the number of columns?

That's what it looks like.
However, it doesn't even matter which way you look at it, and anyway you could just try both ways, so no reason to ask a question like this.