1029 - 3BV
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 40
Solved: 10
- Description
- This problem is based on the game Minesweeper, so I will give a brief introduction on this game first. A rectangle is divided into some square grids, some of them is buried with a mine in it. Let’s call two grids neighborhood if they are orthogonal neighborhood or diagonal neighborhood. The rules are as following:
1. When you click on a grid that doesn’t contain a mine, it will be uncovered.
2. When one grid is uncovered, it will show how many mines in the neighborhood of it.
3. Whenever a grid is uncovered and the number it shows (as rule 2) is 0, all the neighborhood of it will be uncovered automatically.
In the game, there is an important figure for every mine-map ---- 3BV, which is short for Bechtel's Board Benchmark Value. The definition of 3BV is the least number of clicks you need to uncover all the grids that do not contain a mine.
As we know, every thing has the opposite side, we can define another figure of a mine-map ---- SBV, the most number of clicks you can have to uncover all the grids that do not contain a mine(assuming no clicks on the uncovered grids).
As we have mentioned above, you have no operations other than dig a grid with a click. Now, you task is like this----given a mine-map, calculate its 3BV and SBV. - Input
- First line: an integer t, denoting number of test cases.
For every case:
First line: three integer w, h (0<h, w<100), n(0<n<h*w). h is the height of the map, while w is the width of the map, n is the number of mines.
Each of the following n lines: 2 integers xi (0<xi<=w), yi (0<yi<=h), indicating the position of the i-th mine.
- Output
- For each case output two integers in one line, separated by one space:
3BV SBV
- sample input
-
1 2 2 1 1 1
- sample output
-
3 3
- hint
- source
- Xu Han