题目描述

给定一个由若干相连邮票组成的矩形网格（如3×3、4×4等），每次可剪掉一张邮票，要求最终剩余的邮票必须连通（上下左右相邻）。求合法的剪法总数。

输入格式

第一行输入邮票网的大小数据，邮票的行数与列数，接下来输入矩形网格数据，表示邮票位置。

输出格式

输出合法的剪法总数数据

样例

输入样例 1

3 3
0 0   0 1   0 2
1 0   1 1   1 2
2 0   2 1   2 2

输出样例 1

合法的剪法总数为：218

输入样例 2

3 3
-1 -1  0 1  0 2
1 0     1 1  1 2
2 0     2 1  2 2

输出样例 2

合法的剪法总数为：118

输入样例 3

3 3
0 0    0 1    0 2
1 -1  1 -1   1 2
2 0    2 1    2 2

输出样例 3

合法的剪法总数为：30

提示

解题思路：1.DFS枚举删除顺序：从所有邮票中选择保留k张（k从1到总邮票数-1），通过DFS生成所有可能的删除顺序组合。例如，3×3邮票可剪掉1-8张，需枚举所有组合。 2.BFS检查连通性：对每种删除后的剩余邮票集合，以任意一张邮票为起点，用BFS遍历所有可达邮票，判断是否覆盖所有剩余邮票。 若遍历到的邮票数量等于剩余总数，则连通；否则不连通。