← 返回题单

题单练习挑战赛普及/提高- 题

← 上一题下一题 →

A1771 | $迷宫L$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在一个黑暗的迷宫中，你需要找到通往自由的道路。迷宫由一个 $n \times m$ 的矩阵表示，每个单元格要么是墙壁（用数字 $0$ 表示），要么是通道（用数字 $1$ 表示）。 你发现了一个特殊的技巧，可以帮助你找到更多的通道。这个技巧是选择一个 $2 \times 2$ 的子矩阵，在这个子矩阵中选择一个 L 形，将这个 L 形里的 $3$ 个通道单元格变成墙壁（将数字 $1$ 变成 $0$）。注意，这个 $L$ 形至少含有一个通道单元格。 你想要最大化使用这个技巧的次数，以便找到尽可能多的通道并逃离迷宫。请问你最多可以使用这个技巧多少次？

输入格式

输入的第一行包含一个整数 $t$ ($1 \leq t \leq 500$) 表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \leq n, m \leq 500$) 表示迷宫的行数和列数。 接下来的 $n$ 行每行包含一个长度为 $m$ 的二进制字符串，表示矩阵的描述。 保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $1000$。

输出格式

对于每个测试用例，输出可以进行的最大操作次数。

输入输出样例

输入 #1

输出 #1

在第一个测试样例中，一种最优的操作顺序如下（红色字体表示进行操作的 $L$ 形图案）： 进行任何操作之前的矩阵： 101111011110 进行 $1$ 次操作后的矩阵： 1$\color{red}0$$\color{red}0$1$\color{red}0$1011110 进行 $2$ 次操作后的矩阵： 10$\color{red}0$1$\color{red}0$$\color{red}0$011110 进行 $3$ 次操作后的矩阵： 1001$\color{red}0$$\color{red}0$01$\color{red}0$110 进行 $4$ 次操作后的矩阵： 100$\color{red}0$$\color{red}0$0$\color{red}0$10110 进行 $5$ 次操作后的矩阵： 10000001$\color{red}0$1$\color{red}0$$\color{red}0$ 进行 $6$ 次操作后的矩阵： 1000$\color{red}0$00$\color{red}0$$\color{red}0$100 进行 $7$ 次操作后的矩阵： $\color{red}0$$\color{red}0$0$\color{red}0$00000100 进行 $8$ 次操作后的矩阵： 000000$\color{red}0$00$\color{red}0$$\color{red}0$0 在样例中的第三个测试样例中，我们无法执行任何操作，因为矩阵中没有任何 $1$。 在样例中的第四个测试样例中，无论我们在第一次操作中选择哪个 $L$ 形图案，最终都会剩下一个 $1$。因此，我们将执行 $2$ 次操作。

C++ 编辑器

输入

输出