|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||12||8||8||66.667%|
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:
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.
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