题目描述

你最近被一家著名包裹快递公司聘为首席决策官（CDM），恭喜！客户喜欢包裹的快速送达，你决定缩短包裹在全球范围内的递送时间以赢得客户。你已向当局提出这一想法，他们拨给你足够的预算，最多可以新建一个快递办公室。

世界可以划分为一个 $R \times C$ 的网格。每个格子可能包含快递办公室，也可能没有。你可以选择一个尚未包含快递办公室的格子，并在那里新建一个快递办公室。

某个格子的包裹递送时间定义为：如果该格子有快递办公室，则为 $0$；否则，定义为该格子到任何一个有快递办公室的格子的曼哈顿距离的最小值。整体递送时间则是所有格子递送时间的最大值。请问，在最多新建一个快递办公室的情况下，你能获得的最小整体递送时间是多少？

注意：两个格子 $(r1, c1)$ 和 $(r2, c2)$ 之间的曼哈顿距离定义为 $|r1 - r2| + |c1 - c2|$，其中 $|*|$ 表示绝对值。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含网格的行数 $R$ 和列数 $C$。接下来的 $R$ 行，每行包含一个由 $\{0, 1\}$ 中字符组成的长度为 $C$ 的字符串，其中 $0$ 表示该格子没有快递办公室，$1$ 表示有快递办公室。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在最多添加一个快递办公室后你能获得的最小整体递送时间。

3
3 3
101
000
101
1 2
11
5 5
10001
00000
00000
00000
10001

Case #1: 1
Case #2: 0
Case #3: 2

提示

在样例 #1 中，通过在任意一个没有快递办公室的五个格子中新建一个快递办公室，你可以获得最小整体递送时间 $1$。

在样例 #2 中，所有格子都已经有快递办公室，因此最小整体递送时间为 $0$。注意，你最多只能添加一个快递办公室。

在样例 #3 中，为了获得最小整体递送时间 $2$，你可以在以下任意一个格子中新建快递办公室：$(2, 3)$、$(3, 2)$、$(3, 3)$、$(3, 4)$ 或 $(4, 3)$。任何其他选择都会导致整体递送时间大于 $2$。

限制条件

$1 \le T \le 100$。

初始网格中至少有一个快递办公室。

测试集 1（可见）

$1 \le R \le 10$。

$1 \le C \le 10$。

测试集 2（隐藏）

$1 \le R \le 250$。

$1 \le C \le 250$。

翻译由 DeepSeek V4 Pro 完成