主要思路:
状态表示:使用二维布尔数组表示网格状态,True表示该位置被积木覆盖
积木类型:生成所有可能的1×3(横向)和3×1(纵向)积木位置
放置规则检查
小钟在一张长为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个字符为"*",否则为"."。
输出一个整数,表示网格图最终可能的局面个数。
输入
4 4
....
...*
.*..
....
输出
2
说明
对于第一个样例,两种可能的游戏结束局面如下: . * . .
. * . *
. * . *
. . . *
. . . .
. * * *
. * * *
. . . .
输入
3 3
***
***
***
输出
1
说明
对于第二个样例,可以横着摆三行每行一个积木,也可以纵着摆三列每列一个积木,但是这两种方式所导致的最终的局面是相同的,因此可能的局面数是1。