### 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)

zhxl0903on Mar 31, 2009 - 8:55:43 pm UTC m and n?SourSpinachon Mar 31, 2009 - 10:03:15 pm UTC Re: m and n?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.