623 . Development
Description
Development of unused land is an essential first step for creation of infrastructure. An
entrepreneur ventures into a project for creation of a state-of-the-art health-care centre in a
city. Government is prepared to allocate under certain conditions, a part of an unused block of
land for the project. The block exists in the form of an MxN grid of square plots each of unit
area. The entrepreneur has estimated for each plot, the cost of development in certain unit
and rounded it to an integer. He requires for the project, a total number of K connected plots.
However he is allowed to select only a rectangular/ square block of plots so that at least one
side of the selected block either coincides with or is a part of a side of the existing block. In
addition, on removal of the selected block, plots in the existing block should remain
connected.
Given the cost of development for each plot in the grid and the total number K of plots
to be selected, write a program to select all feasible blocks (say b in number), for each one of
which the total cost of development C is the least.
Tables below illustrate the selection of all 3 feasible blocks (b=3), each containing 4
plots (K=4) with least total cost of development (C=47). Integers on the grid represent cost of
development of plots and shaded plots identify selected blocks.
Input Format
Input may contain multiple test cases.
For each test case the first line gives three integers M, N and K as defined above.
Each of the next M lines contains N integers; the jth integer in the ith line represents the cost of development of the plot in ith row and jth column of the grid.
Input terminates with a line containing 0 as the first input for a test case.
Output Format
For each test case, print in the first line, the least total cost of development C and the total number of feasible blocks b.
The first line is followed by b more lines; each line contains two pairs of integers
identifying a feasible block. The 1st pair identifies the first and the last row of the selected
block, while the 2nd pair identifies the first and the last columns of the block. The lines appear in lexicographic order.
Sample Input 1
3 4 4 3 20 29 6 21 9 6 11 7 10 25 5 3 4 3 3 20 29 6 21 9 6 11 7 10 25 5 0
Sample Output 1
47 3 2 3 1 2 2 3 3 4 3 3 1 4 22 1 1 3 4 4
Hints
Problem Source
Migrated from old NTUJ.
ICPC Kanpur, 2008
Subtasks
| No. | Testdata Range | Score |
|---|