Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2636
Repair the Roof

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

Poor Windprayer. This time a terrible hurricane has seriously damaged the roof of his house. Now he wants to repair it with minimum cost.

You can consider the roof as a N by M rectangle, each grid is associated with a damage value, indicating the degree of damage of that grid (a grid is all right and shouldn't to be repaired if the damage value is 0).

Only 1*2 and 2*1 woods are available to repair the roof, and for some visual reason Windprayer will buy woods of same spec and same price. A piece of wood can be used to repair the roof if the price of it is not less than the sum of damage value of the two grids it covers.


The input file contain several test cases, each test case begin with two integers N and M (2 <= N, M <= 50), which is size of the roof. N lines follow, each with M non-negative integer not greater than 10000000, showing the damage value.


For each test case, if it's impossible to repair the roof, output "pat", otherwise, output the minimum cost in the first line, then in each of the following lines, output "(X1,Y1) (X2,Y2)", where (X1, Y1) and (X2, Y2) are positions that piece of wood will cover.

Sample input:

2 2
1 2
3 4

2 2
0 1
1 1

Sample output:

(0,1) (1,1)
(1,0) (0,0)


In test case 1, all grids need to be covered and covering them vertically gains the minimum cost. But in test case 2, only 3 grid need to be covered, and you cannot make it with only 1*2 and 2*1 woods.

Author: JIAO, Xiantao
Source: ZOJ Monthly, December 2005
Submit    Status