第四题　巧置挡板

提交文件：baffles.pas/c/cpp
输入文件：baffles.in
输出文件：baffles.out

猫猫送走了客人，留住了蜗牛点点，晃晃悠悠走到池子边，又打起了鱼的主意。俯瞰池子，猫猫发现鱼阵明显乱了。“难道鱼们故意让我无法下嘴？”猫猫看到正在池边散步的点点，心想：“一定是他告的密……”猫猫愤怒地抓起点点，把他关进了抽屉里。
猫猫想：“好啊，鱼儿啊，你们不就是会传递信息吗？有什么了不起？用挡板把你们隔离开，看你们还怎么交流！”猫猫随即从后花园里拿来若干挡板，打算用这些挡板在水中设立“隔离室”，把鱼们分开。
池塘已经被猫猫抽象成了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


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

输入样例：
4 3
0 1 0
0 0 0
1 0 1
0 0 0

输出样例：
5

上一页  [1] [2] [3] [4]