Time Limit:1.5s Memory Limit: 256MB

题目描述

544带着k个妹子去开房了!他们来到了一家酒店,酒店房间的布局是一张n×m的网格图,有的房间已经有人入住或者被预定了,用1表示,有些房间是空闲的,用0表示。所有房间都是单人间,于是正直的544开了k+1个房间。但是544希望尽可能的靠近所有妹子。具体的,他希望到所有妹子的切比雪夫距离的最大值达到最小。544想知道这个值最小是多少,现在544把问题交给了你,你能回答他吗?

注: 两点\((x1,y1)(x2,y2)\)的切比雪夫距离为\(max(abs(x1-x2),abs(y1-y2))\),其中\(abs(x)\)表示\(x\)的绝对值。

输入格式

第一行是一个正整数\(T\),代表测试数据组数\(1<=T<=10\)。每组测试数据的第一行有三个正整数\(n,m,k(1<=n,m<=1000,1<=k<=10^6)\),含义如上。

接下来的\(n\)行,每行包含一个长度为\(m\)的01字符串,表示房间的空闲情况。输入数据保证不会出现住不下的情况。

输出格式

每组测试一行,先输出“Case#”和测试编号,后面冒号和一个整数(具体请参考样例),代表544和所有妹子距离的最大值的最小值。

样例输入

2 
4 6 5 
011001 
100111 
011100 
011101 
1 10 3 
1010010100

样例输出

Case #1: 2 
Case #2: 3