Skip to content

1104: 捉迷藏

题目

题目描述

大包和小包在玩捉迷藏。小包产生了若干分身分布在$N * M$的矩阵中,并随机地附身于其中一个分身中。大包可以选择任意一个子矩阵并检查其中所有的分身是否为小包的真身。大包当然想要检查尽可能多的分身,但是小包规定大包选出的子矩阵必须是完美的,即子矩阵中的所有位置必须都有一个分身。大包只有一次机会,他想知道自己最多能检查多少个分身。但是大包很憨,作为大包的好朋友,你能帮帮大包吗?

输入格式

第11行,两个正整数$N, M$;

第$2 \sim N+1$行,每行包含$M$个用空格隔开的数字0或1描述矩阵中的状态,0代表该位置没有小包的分身,1代表该位置有一个小包的分身。

输出格式

一行,一个整数表示答案,即大包最多可以检查多少个小包的分身。

样例输入

4 4

1 1 0 1

1 0 1 0

0 1 1 1

1 1 1 0

样例输出

4

数据范围

对于15%的数据,$1 \leq N,M \leq 20$

对于25%的数据,$1≤N,M≤200$

对于75%的数据,$1≤N,M≤1000$

对于100%的数据,$1 \leq N,M \leq 3000 $

时间限制:1s

空间限制:256MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!