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

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:

- The cell is either in the same row or in the same column as your retirement cell; and
- There are no block cells on the straight line between the cell and your retirement cell.

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.

- The first line of input will contain one line with four space-separated
integers R C B F, representing the number of rows and columns in the
grid, respectively, and the number of block cells and fruit cells in the grid,
respectively.
- The following B lines of input will each contain two space-separated
integers describing the row and column of a block cell.
- The following F lines of input will each contain two space-separated
integers describing the row and column of a fruit cell.

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.

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

4

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.

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

- For Subtask 1 (10 points), 1 ≤ R, C ≤ 100.
- For Subtask 2 (50 points), 1 ≤ R, C ≤ 1,000.
- For Subtask 3 (15 points), B = 0. That is, there are no block cells.
- For Subtask 4 (25 points), no further constraints apply.

Privacy
statement

© Australian Mathematics Trust 2001-2021

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