AIOC Banner

Problem: Pam-Can Retires

Want to try solving this problem? You can submit your code online if you log in or register.

Pam-Can Retires

Input File: standard input
Output File: standard output
Time Limit: 1 second
Memory Limit: 256 MB

After spending the last thirty-five years roaming maze after maze and fleeing from ghosts and goblins you - the once world famous PAM-CAN - have decided to retire somewhere in the blissful estate known only as Level 257.

Level 257 is a grid of cells with R rows and C columns. The rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Every cell is either blocked off by uninhabitable mountains (a block cell), contains fruit (a fruit cell) or is completely empty.

You resolve to pick precisely one of these cells as your retirement cell. This cell should either be a fruit cell or completely empty - it cannot be a block cell. From it, you may be able to see other grid cells. Specifically, a cell is visible from your retirement cell if and only if:

Note that your retirement cell is always visible from itself. The diagram below shows a possible layout for Level 257 (on the left) and all visible cells (shaded) if you choose your retirement cell to be at row 1, column 4 on the grid (on the right).


As you ponder your future you ask yourself: "What is the maximum number of fruit cells that could be visible from my retirement cell?" You shudder at the thought of never seeing your beloved fruit again so you decide to write a program to answer this question for you.


Every cell will be described at most once in the input. Every cell that is not described in the input is completely empty.


Your program must output a single integer: the maximum number of fruit cells that are visible from a valid retirement cell. You are guaranteed that there is at least one valid retirement cell in every testcase.

Sample Input

4 5 4 7
2 3
3 2
2 5
1 2
2 2
1 1
1 3
4 4
1 5
2 4
4 1

Sample Output



If you retire to row 1, column 4, you will be able to see the fruit at coordinates (1,3),(1,5),(2,4),(4,4) for a total of 4 fruit. Note that you will not be able to see the fruit at location (1,1) as it is blocked by location (1,2). No other square can see more fruit, therefore the answer is 4.

Subtasks & Constraints

For all subtasks, 1 ≤ R, C ≤ 100,000 and 0 ≤ B + F ≤ 100,000. Additionally, all cells have a row number between 1 and R (inclusive) and a column number between 1 and C (inclusive).


Privacy statement
© Australian Mathematics Trust 2001-2021

Page generated: 21 September 2021,  9:16am AEST