CF1731D Valiant's New Map

游戏工作室“DbZ Games”想在他们热门游戏“Valiant”中引入另一张新地图。这一次，名为“Panvel”的地图将以孟买市为原型。 孟买可以用一个 $n \times m$ 的网格表示。网格中的每个单元格 $(i, j)$（$1 \le i \le n$；$1 \le j \le m$）都被一个高度为 $a_{i,j}$ 的立方体建筑占据。 这一次，DbZ Games 希望制作一张具有完美垂直玩法的地图。因此，他们想在孟买中选择一个 $l \times l$ 的正方形区域，使得该正方形内的每一座建筑的高度都至少为 $l$。 你能帮助 DbZ Games 找到这样一个最大可能边长 $l$ 的正方形吗？

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \leq t \leq 1000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个正整数 $n$ 和 $m$（$1 \le n \le m$；$1 \leq n \cdot m \leq 10^6$）。 接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$（$1 \leq a_{i,j} \leq 10^6$），表示第 $i$ 行每座建筑的高度。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

对于每个测试用例，输出 DbZ Games 可以选择的正方形的最大边长 $l$。

在第一个测试用例中，我们可以选择边长 $l = 2$ 的正方形（即整个网格），因为所有建筑的高度都大于等于 $2$。 在第二个测试用例中，我们只能选择边长为 $1$ 的正方形，所以答案是 $1$。 在第三个测试用例中，没有边长为 $2$ 的正方形能满足所有建筑高度至少为 $2$，所以答案是 $1$。 由 ChatGPT 4.1 翻译