감시 로봇

시간 제한1초메모리 제한128 MB

요약
장애물로 나뉜 행과 열 구간을 노드로 삼아 이분 그래프를 만들고 최대 매칭으로 최소 정점 커버를 구해 필요한 로봇 수를 계산하는 문제입니다.
난이도

보통10점 중 7점

유형
그래프, 유니온 파인드, 행렬
정답자
아직 제출이 없습니다

문제

관심 지점들을 감시 로봇으로 지켜야 합니다. 로봇은 이동하거나 회전할 수 없습니다. 로봇은 격자의 임의의 칸에 놓을 수 있으며, 북·남·동·서 중 한 방향을 바라보게 배치합니다. 한 번 놓인 로봇은 자신이 바라보는 방향의 정면에 있는 관심 지점들을, 장애물에 시야가 막힐 때까지 모두 감시합니다. 같은 행 또는 같은 열에 있고 로봇과의 사이에 장애물이 없는 두 개 이상의 관심 지점은 로봇 하나로 한꺼번에 감시할 수 있습니다.

관심 지점과 장애물이 놓인 격자가 주어질 때, 모든 관심 지점을 감시하는 데 필요한 로봇의 최소 개수를 구하세요. 어떤 관심 지점은, 그 방향을 바라보는 로봇이 있고 그 사이에 장애물이 없을 때 감시됩니다.

아래 격자에서 #는 장애물, *는 관심 지점을 나타냅니다. 필요한 로봇의 최소 개수는 2이며, 가능한 배치와 방향 하나를 화살표로 표시했습니다. 이는 이해를 돕기 위한 그림일 뿐, 실제 입력이나 출력 형식이 아닙니다.

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

다음 격자에서는 장애물 때문에 로봇 4개가 필요합니다.

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

입력

첫 번째 줄에는 테스트 케이스의 수를 나타내는 정수 CC가 주어집니다. 각 테스트 케이스 앞에는 빈 줄이 하나씩 있습니다.

각 테스트 케이스의 첫 줄에는 격자의 높이 YY와 너비 XX를 나타내는 두 정수가 주어집니다. 그다음 줄에는 관심 지점의 개수 PP가 주어지고, 이어지는 PP개의 줄에 각 관심 지점의 좌표 pyp_y와 pxp_x가 한 줄에 하나씩 주어집니다. 그다음 줄에는 장애물의 개수 WW가 주어지고, 이어지는 WW개의 줄에 각 장애물의 좌표 wyw_y와 wxw_x가 한 줄에 하나씩 주어집니다.

출력

각 테스트 케이스마다 모든 관심 지점을 감시하는 데 필요한 로봇의 최소 개수를 한 줄에 하나씩 출력하세요.

제약 조건:

  • 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

예제1

  1. 예제 1

    입력
    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
    예상 출력
    2
4