RQNOJ系统遇到了一个程序错误。

您可以通过邮件support (at) rqnoj.cn与我们进行联系。请附错误参考编号:387851

巧置挡板 - 题库 - RQNOJ
PID187 / 巧置挡板
题目描述

猫猫送走了客人,留住了蜗牛点点,晃晃悠悠走到池子边,又打起了鱼的主意。俯

瞰池子,猫猫发现鱼阵明显乱了。“难道鱼们故意让我无法下嘴?”猫猫看到正在池边散

步的点点,心想:“一定是他告的密……”猫猫愤怒地抓起点点,把他关进了抽屉里。

猫猫想:“好啊,鱼儿啊,你们不就是会传递信息吗?有什么了不起?用挡板把你

们隔离开,看你们还怎么交流!”猫猫随即从后花园里拿来若干挡板,打算用这些挡板

在水中设立“隔离室”,把鱼们分开。

池塘已经被猫猫抽象成了n行m列小方格,每个小方格中或有鱼,或无鱼。挡板必

须沿着小方格的边缘放置。猫猫需要用挡板围出若干个“隔离室”,使得每个隔离室中

有且只有一条鱼,而且,每个“隔离室”都必须为矩形(包括正方形)。

那么,将鱼们隔离开来,猫猫最少需要多少个长度单位的木板呢?

例如:

n=4,m=3时的一种情况(0表示小方格内无鱼,1表示有鱼)。

0 1 0

0 0 0

1 0 1

0 0 0

可以这么分:

0 1 0

0 0 0

1 0 1

0 0 0

由于池塘边框不需要放置挡板,所以这个分割方案所需的挡板总长度为5。

输入格式

第一行有两个整数n和m,描述池塘规模。接下来的n行,每行有m个数字(非

“0”即“1”)。每两个数字之间用空格隔开。

对于20% 的数据,有1≤n,m≤10

对于40% 的数据,有1≤n,m≤16

对于70% 的数据,有1≤n,m≤24

对于100%的数据,有1≤n,m≤32

输出格式

对于每组输入数据,输出一行:一个数字,猫猫所需挡板的最短总长度。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论