시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB31212170.000%

문제

There has been a huge storm ravaging through Manhattan destroying many power-lines and leaving entire blocks without power. The first damage assessment came up with a report showing which blocks are still connected by power lines and which are not. When a block is connected to another block with power lines, this means that if one block has power, then the other will also have power. Only blocks that are adjacent (either horizontally, or vertically) may be connected by a power line. Also, there is a quickly made list with all blocks that have power generators, or that are connected to external power sources.

Your task is to quickly identify where to put up emergency power lines, so that all block of this grid-like city have power again.

입력

The input starts with a line containing an integer T, the number of test cases. Then for each test case:

  • One line with four integers, n, m, p, c, where n, m (1 ≤ n, m ≤ 100) are the number of blocks that the city is wide respectively long (the city has n x m blocks), p (1 ≤ p ≤ n · m) is the number of power generators, and c (1 ≤ c ≤ 2n · m, or in fact: 1 ≤ c ≤ 2n · m − n − m) is the number of intact power lines between adjacent city blocks.
  • p lines, each with two integers x (0 ≤ x < n), y (0 ≤ y < m) indicating that the block with coordinates (x, y) in the grid has its own power source or is connected to an external power source.
  • c lines, each with two integers x (0 ≤ x < n), y (0 ≤ y < m), and a character d (d = ’R’ or d = ’U’) indicating that there is an intact power line either between block (x, y) and block (x + 1, y) if d = ’R’, or between block (x, y) and block (x, y + 1) if d = ’U’. Of course, if x = n − 1, then d cannot be ’R’. Likewise, if y = m − 1, then d cannot be ’U’.

출력

Per test case, output one line with one integer indicating the number of emergency power lines needed to connect all blocks to a power source.

예제 입력 1

2
2 3 2 3
0 2
1 1
0 0 U
0 2 R
1 1 U
2 4 2 6
0 3
1 0
0 0 U
0 1 U
0 1 R
0 2 R
0 3 R
1 1 U

예제 출력 1

2
1

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2015 Preliminaries F번

  • 문제를 만든 사람: Johan van Rooij