시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 512 MB | 5 | 3 | 3 | 100.000% |
Daryl owns a disco dance club named the Disco Dance Den. It has a disco dance floor which is in the shape of an m × n grid. At first, all of these cells are lit up. When the music starts playing, some cells of this grid become unlit.
A disco dance is a sequence of at least two steps done by a disco dancer while the music plays. The last step of a disco dance must be on the disco dancer’s starting cell.
A disco dancer only steps on lit cells while doing a disco dance. At the exact moment he steps on a lit cell, it immediately becomes unlit. Moreover, a disco dancer always satisfies the following four conditions:
Now, we say that Daryl’s Disco Dance Den is dark if all the cells of the disco dance floor becomes unlit.
Daryl discusses a disco dare with a group of disco dancers in his den. The disco dare goes as follows:
As an example, if this is the setup:
Then the disco dare can be done by having two disco dancers start at the cells indicated in the left side of the figure below:
After all the disco dancers finish their disco dance, Daryl’s Disco Dance Den is expected to go dark since all the lit cells have been stepped on. In addition, the two disco dancers on the dance floor satisfied all four conditions a disco dancer must satisfy.
Is it possible for them to do the disco dare they discussed with Daryl? If not, what is the smallest number of cells that must change their state (from lit to unlit, or vice-versa) so that it becomes possible for them to do the disco dare?
The first line of input contains a single integer T, the number of test cases. The following lines describe the test cases.
The first line of each test case contains three space-separated integers m, n and k, in that order, specifying the number of rows and columns of the grid, respectively, and the number of groups of cells which will become unlit once the music starts.
The next k lines describe which cells of the disco dance floor become unlit when the music starts. Each of these lines contain four space-separated integers i0, j0, i1, j1. This tells us that for all i and j that satisfy i0 ≤ i ≤ i1 and j0 ≤ j ≤ j1, the cell on the ith row and jth column becomes unlit when the music starts.
Note: The groups of unlit cells may overlap.
Constraints
For each test case, one line containing a single integer N, which is the smallest number of cells whose states must change so that the disco dancers can complete Daryl’s disco dare.
3 5 5 4 1 1 2 3 1 3 3 3 3 4 5 5 5 1 5 1 4 4 8 1 1 1 1 1 3 1 3 2 2 2 2 2 4 2 4 3 1 3 1 3 3 3 3 4 2 4 2 4 4 4 4 1 2 0
1 0 2
The first sample input shows that the groups of unlit cells may overlap. The solution is to flip just one cell, namely (4,2), so it becomes just like the grid shown in the images above.