1214. [Balkan2007]Monsters
#1214. [Balkan2007]Monsters
题目描述
人类最终登陆了人马座行星，却惊讶地发现这颗行星是怪物的聚居地。这些怪物的防御系统是一个N行M列的矩阵格。
人类的星际舰队已经击破了一些单元格，但是现在轮到你来决定摧毁哪一个单元格了。
怪物的防御系统的防御力由只包含完整单元格的子矩阵的数量决定。
一个非空子矩阵由原矩阵通过以下方法获得：
一、移除一些以第一行开始的连续的行
二、移除一些以最后一行结束连续的行
三、移除一些以第一列开始的连续的列
四、移除一些以最后一列结束连续的列
选择一个单元格来摧毁，使得最小化防御系统的防御力
任务
计算摧毁一个单元格后，防御系统的防御力的最小值
输入格式
第一行包括两个用空格隔开的两个数字N和M，表示矩阵的行数和列数。
接下来有N行，每行一串长度为M的01串。1表示该单元格是完整的，0表示该单元格已经被摧毁了。
1 <= N , M <= 750
对于所有的数据，矩阵里至少有1个完整的单元格
输出格式
输出一个数字，即摧毁一个单元格以后，防御系统的防御力的最小值。
样例
样例输入
3 3
011
110
100
样例输出
6
样例解释
最初时，防御系统的防御力是9。摧毁第二行第二列的单元格以后，防御力降为6。
此时的矩阵为
011
100
100