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