Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
One is good, but two is better
Time Limit: 2000MSMemory Limit: 65536K
Total Submissions: 453Accepted: 160

Description

Given the N by M matrix with elements equal either 0, 1 or 2, There is at least one element equal to 2. Your program must find such two (perhaps overlapping or even identical) rectangles, that they would contain all the 2s which are in matrix, but none of the 1s. If several solutions exist, the program must find a solution with minimal area of joined rectangles. For example, in the matrix
 1 2 1 0

2 0 2 2
1 2 1 0

these rectangles are (2,1)-(2,3) and (1,2)-(4,2), with the combined area of 6.

Constraints
1 ≤ N, M ≤ 50

Input

Input contains integers N and M followed by N * M matrix elements.

Output

Output must contain a single integer -- the minimal area, or -1 if no solution exists

Sample Input

3 4
1 2 1 0
2 0 2 2
1 2 1 0

Sample Output

6

Source

Northeastern Europe 2003, Far-Eastern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator