P12106 [NWRRC2024] Brick in the Wall, Part 2

Barrett 在他的房子下方发现了一个古老的迷宫。该迷宫呈 $n \times m$ 网格状，其中部分格子为空地，其他则为障碍物。若两个空格子共享一条边，则可以从一个格子走到另一个。迷宫中有一个入口格子和一个出口格子，且可以通过空格子从入口走到出口。 Barrett 希望通过在迷宫中建造一堵墙来隔离他的房子，通过阻挡部分格子使得出口无法从入口到达。这堵墙必须是笔直的，且方向只能是垂直或水平。具体而言，长度为 $k$ 的墙将阻挡恰好 $k$ 个连续的行或列格子。墙不能包含入口、出口或任何已有障碍物的格子。 请帮助 Barrett 确定这堵墙的最小可能长度。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示迷宫的高度和宽度（$2 \le n, m \le 1000$）。 接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个字符，描述迷宫的第 $i$ 行，其中： - $\texttt{.}$ 表示空格子； - $\texttt{\#}$ 表示障碍物格子； - $\texttt{s}$ 表示入口格子； - $\texttt{f}$ 表示出口格子。 迷宫中恰好有一个入口格子和一个出口格子，且可以通过空格子从入口走到出口。 保证所有测试用例的 $n \cdot m$ 之和不超过 $10^6$。

对于每个测试用例，输出使得出口无法从入口到达所需建造的墙的最小长度。 如果无法建造这样的墙，则输出 $-1$。