F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 1214. -- [Balkan2007]Monsters

1214: [Balkan2007]Monsters

Time Limit: 20 Sec  Memory Limit: 32 MB
Submit: 1313  Solved: 7
[Submit][Status][Discuss]

Description

人类最终登陆了人马座行星,却惊讶地发现这颗行星是怪物的聚居地。这些怪物的防御系统是一个N行M列的矩阵格。
人类的星际舰队已经击破了一些单元格,但是现在轮到你来决定摧毁哪一个单元格了。
怪物的防御系统的防御力由只包含完整单元格的子矩阵的数量决定。
一个非空子矩阵由原矩阵通过以下方法获得:
一、移除一些以第一行开始的连续的行
二、移除一些以最后一行结束连续的行
三、移除一些以第一列开始的连续的列
四、移除一些以最后一列结束连续的列
选择一个单元格来摧毁,使得最小化防御系统的防御力
任务
计算摧毁一个单元格后,防御系统的防御力的最小值

Input

第一行包括两个用空格隔开的两个数字N和M,表示矩阵的行数和列数。
接下来有N行,每行一串长度为M的01串。1表示该单元格是完整的,0表示该单元格已经被摧毁了。
1 <= N , M <= 750
对于所有的数据,矩阵里至少有1个完整的单元格

Output

输出一个数字,即摧毁一个单元格以后,防御系统的防御力的最小值。

Sample Input

3 3
011
110
100

Sample Output

6
样例解释
最初时,防御系统的防御力是9。摧毁第二行第二列的单元格以后,防御力降为6。
此时的矩阵为
011
100
100

HINT

Source

[Submit][Status][Discuss]

HOME Back