ACM International Collegiate Programming Contest, Tishreen Collegiate Programming Contest (2017) |
---|
Finished |
Have you ever played Minesweeper? It’s a cute little game that originates from the 1960s, and has been written for many computing platforms in use today.
The game consists of a two dimensional grid, and there are two types of cells in it.
A mined cell, and an empty cell, which contains a single digit that indicates how many adjacent cells contain mines. Eech cell has at most 8 adjacent cells.
In this version of the game, you are going to build a level with the following rules:
For instance, the following is 4 * 5 valid grid with 12 mines (which are represented by an '*' character) and the maximum number for the empty cells is M = 3 :
* * * * 2
* * * * 2
3 * * 3 1
We are interested in the maximum number of mines that a grid with those properties can contain, can you find the answer for us?
The first line contains a single integer T denoting the number of test cases.
Each test case consists of one line which contains three space separated integers:
The number of the rows in the grid r. (2 ≤ r ≤ 6).
The number of the columns in the grid c. (2 ≤ c ≤ 6).
The maximum number that any empty cell can contain. (1 ≤ M ≤ 8).
For each test print one line containing one integer, the maximum number of mines that a grid can contain.
2
4 5 3
3 3 4
12
6
The grid in the statement is a valid grid for the first sample.
Name |
---|