Problem 1115. -- 菜哭武的房子

1115: 菜哭武的房子

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 87  Solved: 18
[Submit][Status][Web Board]

Description

新格尔公司的天才程序员菜哭武刚刚在市中心买下了一块地,他想自己盖一个别墅,但是由于地点实在是太好,他在修房子的时候必须满足一些要求,在某些地方只能使用某些特定的材料。比如说,从他家门口到马路上的路,只能在设计好的N个1xM的瓷砖序列中选择,他可以决定选择哪些瓷砖,但是不能改变相对顺序,不能旋转或者翻转,并且不能重复选择。每块瓷砖由黑色和白色的小块构成,可以看成一个01字符串,0表示白色的小块,1表示黑色的小块。在走的时候,菜哭武值喜欢走黑色的区域,并且每次他可以移动到前左右相邻的三个格子(不要问我为什么他不可以往其他的方向走,菜哭武就喜欢这样)。他现在的想法是让自己的门尽可能的离马路远一些,由于他家的门还没确定放在哪里,所以只需要连出来一条尽量长的瓷砖序列,选用的瓷砖数量越多越好,并且菜哭武可以按照上述喜好从马路走到别墅。天才程序员菜哭武自然是知道怎么算的,但是他实在是太忙了,所以想让你帮他来算一下。

Input

第一行一个整数T,表示有T组测试数据。(T ≤ 10)
每组测试数据,第一行,包含两个整数,N,M;(N 500 , 2 M 365)
N表示可以选择模块数量,M表示每个模块的长度。
然后有N行,每行是一个长度为M的01串。

Output

对于每组数据,第一行输出Case #x: (x编号从1开始)
然后第二行输出一个整数,表示最长得路有多长。

Sample Input

2
3 3
000
001
100
4 5
00001
11101
10111
10000

Sample Output

Case #1:
1
Case #2:
3

HINT

样例解释:

第一组数据中,第2,3个任意一个均可。

第二组数据中,第1,2,3个或者第2,3,4个两种方案。因为每次走的时候只能选择前左右三个方向,所以全部选择的方案是不可以的。

Source

[Submit][Status]