#1150. 1-01F.czq的疑惑矩阵

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

题目描述

czq获得了一个01矩阵。直觉告诉他,这里面蕴藏了珍贵的宝藏(1分)。然而矩阵的内容却让他十分疑惑,百思不得其解。

无敌的lhz告诉czq,他可以将矩阵的若干位置的数取反。如果矩阵的所有由1组成的和由0组成的极大连通块全部恰好为矩形,那么一切疑惑都会解开。当然,必须取反尽可能少的数才能获取宝藏。蒟蒻的czq不会做,所以他把这题抛给了你。

这里的联通定义为四联通,即一个元素与它上下左右四个元素相邻

输入格式

第一行两个数,为矩阵的大小。

接下来行每行个数,为01矩阵。

输出格式

仅一个整数,为答案。

样例

样例输入

5 5
1 0 1 0 0
1 1 1 1 1
1 1 1 0 1
0 0 0 1 0
1 1 1 0 0

样例输出

4

样例说明

一种可能的答案
1 1 1 0 1
1 1 1 0 1
1 1 1 0 1
0 0 0 1 0
1 1 1 0 1

数据范围与提示