#P2332. One is good, but two is better

    ID: 1333 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>线性代数其他Northeastern Europe 2003Far-Eastern Subregion

One is good, but two is better

描述

给定一个N×MN×M的矩阵,矩阵元素取值为001122,且矩阵中至少存在一个元素值为22。你的程序需要找到两个(可能重叠甚至完全相同)矩形,这两个矩形要包含矩阵中所有值为22的元素,但不能包含任何值为11的元素。如果存在多个满足条件的解,程序必须找出合并后矩形面积最小的那个解。例如,在矩阵

1 2 1 0
2 0 2 2
1 2 1 0

中,这两个矩形分别是(2,1)(2,3)(2,1)-(2,3)(1,2)(4,2)(1,2)-(4,2),合并后的面积为66

约束条件

1N,M501 ≤ N, M ≤ 50

输入

输入包含整数NNMM,随后是N×MN×M个矩阵元素。

输出

输出必须是一个整数,表示最小面积;如果不存在满足条件的解,则输出1-1

输入数据 1

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

输出数据 1

6