#P2332. One is good, but two is better
One is good, but two is better
描述
给定一个的矩阵,矩阵元素取值为、或,且矩阵中至少存在一个元素值为。你的程序需要找到两个(可能重叠甚至完全相同)矩形,这两个矩形要包含矩阵中所有值为的元素,但不能包含任何值为的元素。如果存在多个满足条件的解,程序必须找出合并后矩形面积最小的那个解。例如,在矩阵
1 2 1 0
2 0 2 2
1 2 1 0
中,这两个矩形分别是和,合并后的面积为。
约束条件
输入
输入包含整数和,随后是个矩阵元素。
输出
输出必须是一个整数,表示最小面积;如果不存在满足条件的解,则输出。
输入数据 1
3 4
1 2 1 0
2 0 2 2
1 2 1 0
输出数据 1
6