问题 1097 --【基础】长蛇阵

1097: 【基础】长蛇阵

题目描述

  

小丁是一个地道的“驴友”(特别喜欢旅游),这一天他来到了内蒙古大草原,“哇,好开阔啊!好壮观啊!”,小丁惊呼道。只见草原上许多羊在吃着肥美的嫩草。忽然,小丁大叫一声:“一字长蛇阵”,原来小丁也是一位军事爱好者,平时老爱研究一些兵器、阵法什么的。他发现了一些羊排成了“一字长蛇阵”。而且这样的阵不止一个,他想知道哪一个长蛇阵最长,最长的长蛇阵是由多少只羊连成的。小丁数了半天,眼睛都数花了。所以他想到了你,现给出小丁拍摄的卫星照片,上面记录了每只羊所处的位置,试计算最长的长蛇阵由多少只羊组成。

输入

第1行:两个整数n和m,表示草原有n行m列(0 < n, m <= 1000)
第2..n+1行:每行m个整数,每个整数要么为0,要么为1。为0表示该位置没有羊存在,为1表示该位置有羊。

输出

一行:一个整数,表示最长的长蛇阵的羊的只数,找不到这样的长蛇阵则输出0。

样例输入输出

输入#1 复制
5 6
0 0 0 0 0 0
0 1 0 0 1 0
0 1 1 1 1 0
0 0 1 0 0 0
0 0 0 0 0 0

输出#1 复制
4

提示

输出解释—— 为了便于说明,我们给每只羊编号: 0 0 0 0 0 0 0 1 0 0 6 0 0 2 3 4 5 0 0 0 7 0 0 0 0 0 0 0 0 0 能找到的“长蛇阵”有7个,有1-2;1-3;2-3-4-5;2-7;3-7;5-6;6-4-7(横、竖、斜方向上至少能找到两只羊连在一起的才能算长蛇阵)。最长的一条由4只羊组成。

数据规模—— 40%的数据满足n,m<=100; 100%的数据满足n,m<=1000。

序号 标题 作者 发表时间 费用 订购数 操作