logo AlgoBeat OnlineJudge
登录 注册

#101214. [BZOJ 1214] [Balkan2007]Monsters

内存限制:32 MiB 时间限制:20000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

人类最终登陆了人马座行星,却惊讶地发现这颗行星是怪物的聚居地。这些怪物的防御系统是一个 列的矩阵格。

人类的星际舰队已经击破了一些单元格,但是现在轮到你来决定摧毁哪一个单元格了。

怪物的防御系统的防御力由只包含完整单元格的子矩阵的数量决定。

一个非空子矩阵由原矩阵通过以下方法获得:

  • 移除一些以第一行开始的连续的行;
  • 移除一些以最后一行结束连续的行;
  • 移除一些以第一列开始的连续的列;
  • 移除一些以最后一列结束连续的列。

选择一个单元格来摧毁,使得最小化防御系统的防御力。

你的任务是计算摧毁一个单元格后,防御系统的防御力的最小值。

输入格式

第一行包括两个用空格隔开的两个数字 ,表示矩阵的行数和列数。

接下来有 行,每行一串长度为 01 串。 1 表示该单元格是完整的, 0 表示该单元格已经被摧毁了。

输出格式

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

样例输入

3 3
011
110
100

样例输出

6

数据范围与提示

对于 的数据,,对于所有的数据,矩阵里至少有 个完整的单元格。