All submissions for this problem are available.
In Egypt each year in the rainy season, the province in Byte land is flooded with water. The province has the form of a rectangular land divided into unit cells of M lines and N columns. Some cells are flooded and some cells are not. Each flooded cell has a water depth level which is a positive integer.
Because of flood, the land is divided into several islands, each island consists of the cells that can move around one another but cannot move to cells in different islands. The people can move between two non flooded cells if these cells have at least one common point.
To improve the transportation quality during the flooding season, the Egypt's government decides to raise some flooded cells to become non flooded cells so that after the process, the people are able to travel between any two non flooded cells.
To make a flooded cell whose water depth level is D become non flooded, the workers need to put in D units of clay.
The government wants to achieve the goal using the fewest units of clay possible.
The first line contains t, the number of test cases (about 20), each test case has the following form.
The first line contains two number M and N (1 <= M, N <= 200).
Each line in the next M lines contain N numbers describing the status of each cell in the land. If a cell is not flooded, the corresponding number is -1 while if it is flooded the corresponding number is the cell's water depth level.
Each test case's input is separated by a blank line.
For each test case, output the result in the following format.The first line contains T, the number of units of clay used.The second line contains a number S which is the number of flooded cells needed to raise.Each line in the next S lines contains two numbers representing the row and column index (1-based) of a raised cell.Print a blank line after each test case's output.
For each test case, your program's score is equal to T/H in which H is the number of units of clays to raise all the flooded cell.
Input: 1 3 3 -1 10 -1 10 2 10 -1 10 -1 Output: 2 1 2 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.