CF1898F Vova Escapes the Matrix

在一次环球旅行后，Vova 被困在一个 $n \times m$ 的矩阵中。该矩阵的行编号为 $1$ 到 $n$（从上到下），列编号为 $1$ 到 $m$（从左到右）。第 $(i, j)$ 个格子表示第 $i$ 行第 $j$ 列的格子，其中 $1 \leq i \leq n$，$1 \leq j \leq m$。 矩阵中的某些格子被障碍物阻挡，其他格子为空。Vova 站在某个空格子上。保证 $(1, 1)$、$(1, m)$、$(n, 1)$、$(n, m)$（即矩阵的四个角）都是被阻挡的。 Vova 可以从一个空格子移动到与其有公共边的另一个空格子。Vova 可以从矩阵边界上的任意空格子逃出矩阵，这些格子称为出口。 Vova 根据他可以用来逃出的出口数量，将矩阵分为以下三种类型： - 第 $1$ 类：没有他可以用来逃出的出口的矩阵。 - 第 $2$ 类：恰好有一个他可以用来逃出的出口的矩阵。 - 第 $3$ 类：有两个或更多他可以用来逃出的出口的矩阵。 在 Vova 开始移动之前，Misha 可以在更多的格子上设置障碍物。但他不能改变矩阵的类型。Misha 最多可以阻挡多少个格子，使得矩阵的类型保持不变？Misha 不能阻挡 Vova 当前所在的格子。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$3 \leq n, m \leq 1000$），表示矩阵的大小。 接下来的 $n$ 行描述矩阵的具体情况：第 $i$ 行（$1 \leq i \leq n$）包含一个长度为 $m$ 的字符串，由字符 '.'、'#' 和 'V' 组成。第 $i$ 行第 $j$ 个字符描述了第 $(i, j)$ 个格子。'.' 表示空格子，'#' 表示被阻挡的格子，'V' 表示 Vova 当前所在的空格子（也是空格子）。 保证矩阵的四个角都是被阻挡的（即第一行和最后一行的第一个和最后一个字符都是 '#'）。保证 'V' 在矩阵中只出现一次。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $1\,000\,000$。

对于每个测试用例，输出一个整数，表示 Misha 最多可以阻挡的格子数。

在第一个测试用例中，矩阵属于第 $3$ 类。Misha 可以在除了 $(1, 3)$、$(2, 3)$、$(2, 4)$ 这三个格子以外的所有空格子上设置障碍物，共有 $9$ 个这样的格子，这样不会改变矩阵的类型。 在第二个测试用例中，矩阵属于第 $3$ 类。如果阻挡任意一个格子，矩阵类型就会变成第 $2$ 类：Vova 能到达的出口会减少到一个。因此答案是 $0$。 在第三个测试用例中，矩阵属于第 $1$ 类。除了 Vova 所在的格子外没有其他空格子，因此 Misha 不能阻挡任何格子。 在第四个测试用例中，矩阵属于第 $2$ 类。Misha 可以在 $(5, 2)$、$(6, 3)$、$(6, 4)$ 这三个格子上设置障碍物，而不会改变矩阵的类型。 在第五个测试用例中，矩阵属于第 $3$ 类。Misha 可以在 $(2, 2)$、$(3, 2)$、$(4, 2)$、$(5, 2)$ 这四个格子上设置障碍物，或者在 $(2, 4)$、$(3, 4)$、$(4, 4)$、$(5, 4)$ 这四个格子上设置障碍物，而不会改变矩阵的类型。 由 ChatGPT 4.1 翻译