Sentry Robots

Time limit1sMemory limit128 MB

Summary
Group points of interest into row and column segments split by obstacles and find the minimum vertex cover of the resulting bipartite graph via maximum matching.
Level

Medium7 of 10

Topics
Graph, Union-find, Matrix
Solved
No attempts yet

Problem

We must guard a set of points of interest using sentry robots that cannot move or rotate. A robot can be placed on any grid cell, facing north, south, east, or west. Once placed, a robot guards every point of interest that lies directly in front of it, along the direction it faces, until its line of sight is blocked by an obstacle. Two or more points that lie in the same row or the same column, with no obstacle between them and the robot, can all be guarded by that single robot.

Given a grid of points of interest and obstacles, compute the minimum number of robots needed so that every point of interest is guarded. A point is guarded when some robot faces its direction with no obstacle in between.

In the grid below, # marks an obstacle and * marks a point of interest. The minimum number of robots needed is 2; one valid placement and orientation is shown with arrows. This is only an illustration, not the input or output format.

   Grid             Solution
. . . . . .        . . . . . .
. * # * . .        . * # * . .
. . # . . .        . . # . . .
. * # * . .        . ↑ # ↑ . .

For the next grid, 4 robots are required because of the obstacles.

   Grid             Solution
. * * . .           . → * . .
. * # * .           . ↑ # ↑ .
. # * . .           . # ↓ . .
. . # . .           . . * . .

Input

The first line contains an integer CC, the number of test cases. Each test case is preceded by a blank line.

Each test case begins with a line containing two integers YY and XX: the height and the width of the grid. The next line contains an integer PP, the number of points of interest, followed by PP lines, each giving the coordinates pyp_y and pxp_x of one point. The next line contains an integer WW, the number of obstacles, followed by WW lines, each giving the coordinates wyw_y and wxw_x of one obstacle.

Output

For each test case, print a single line containing the minimum number of robots needed to guard all points of interest.

Constraints:

  • 1≤C≤501 \le C \le 50
  • 1≤Y,X≤1001 \le Y, X \le 100
  • 0≤P≤Y⋅X0 \le P \le Y \cdot X
  • 0≤W≤Y⋅X0 \le W \le Y \cdot X
  • 0≤P+W≤Y⋅X0 \le P + W \le Y \cdot X
  • 1≤px,wx≤X1 \le p_x, w_x \le X
  • 1≤py,wy≤Y1 \le p_y, w_y \le Y

Examples1

  1. Example 1

    Input
    2

4 6
4
2 2
2 4
4 2
4 4
3
2 3
3 3
4 3

4 5
6
1 2
1 3
2 4
2 2
3 3
4 3
2
2 3
3 2
    Expected output
    2
4