## WC '96 P5 - Plentiful Paths

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 16M

Problem type
##### Woburn Challenge 1996

Given is an by grid and on each square of the grid there may or may not be an apple on it. Let be the bottom left square and be the upper right square of the grid. Find the path from to (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 and ).

#### Input Specification

Your program should read in the size of the grid, and , where . The locations of the apples where is at and is at . 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 Specification

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

5