P4356.【深度优先搜索9】积木游戏
本题为2025年8月10日小米机考原题
小米机考的介绍点击这里
题目内容
小钟在一张长为n、宽为m的网格图上摆放积木。图上有一些格子是特殊格子，小钟有无限个尺寸为1×3或3×1的积木。每次小钟摆放积木时，需要满足以下条件:积木至少有一端与特殊格子重合，只能在网格图内摆放，不能越界，且当前要摆放的积木不能与已经摆放的积木发生重叠。小钟会一直按上述要求摆放积木，直到无法再摆放积木为止。
小爱在一旁看着小钟摆放积木，她很好奇网格图最终一共有多少种可能的局面。两种局面不同，当且仅当网格图中存在某个格子，一种局面中该格子被积木覆盖，另一种局面中没有被覆盖。请你计算网格图最终有多少可能的局面。注意，局面的不同与如何摆放无关，仅与格子是否被覆盖有关系!
1≤n,m≤8。保证特殊格子的数量不超过13，数据随机生成。
输入描述
第一行有两个整数n(1≤n≤8)、m(1≤m≤8)，分别表示网格图的长和宽.
接下来n行每行输入m个字符，若网格图第i行第j列位置是特殊格子，则第i行第j个字符为"*",否则为"."。
输出描述
输出一个整数，表示网格图最终可能的局面个数。
样例1
输入
4 4
....
...*
.*..
....
输出
2
说明
对于第一个样例，两种可能的游戏结束局面如下:
. * . .
. * . *
. * . *
. . . *
. . . .
. * * *
. * * *
. . . .
样例2
输入
3 3
***
***
***
输出
1
说明
对于第二个样例，可以横着摆三行每行一个积木，也可以纵着摆三列每列一个积木，但是这两种方式所导致的最终的局面是相同的，因此可能的局面数是1。
