题目链接: 291. 蒙德里安的梦想
主要思路
状态压缩的经典应用
所谓的状态压缩,举个例子,把整数用二进制表示,而且在二进制上状态转移,就是状态压缩。
LC经典题目N皇后的位运算做法也是状态压缩的应用。
这题要算的目标,可以等价为:在矩阵中把横的小块放完的所有方案(因为横的小块放完后,竖的小块的方法就塌缩为1了)
关键是这题目的状态表示和状态转移
- 状态表示 dp[i][j] 表示 j 是 i 的前一列,从 j 延伸过来到 i 的状态
- 状态转移 当没有从 j - 2 延伸过来的于 j - 1 延伸过来的起冲突且竖列没有单个的0, dp[i][j] += dp[i - 1][k]
注意细节
【go语言细节】
涉及大数的读取,这里需要用上bufio + os 的快读快写
其中writer是带缓存的,要将缓存写入文件才能输出答案,因此在最后需要这一句:writer.Flush()
基础代码
package main
import (
"bufio"
"fmt"
"os"
)
const (
N = 12
M = 1 << N
)
var (
reader = bufio.NewReader(os.Stdin)
writer = bufio.NewWriter(os.Stdout)
st [M]bool // 字典表,存储所有位置的合法情况
dp [N][M]int
)
func initStatus(n int) {
for i := 0; i < 1 << n; i++ {
cnt := 0
st[i] = true
for j := 0; j < n; j++ {
// 遇到1,被占, 且统计的空格数为奇数,无法填充竖着的长方形
if i >> j & 1 > 0 {
if cnt & 1 > 0 {
st[i] = false
break
}
cnt = 0
continue
}
cnt++
}
// 判断剩下的统计数是否奇数
if st[i] && cnt & 1 > 0 { st[i] = false }
}
}
func cal(n, m int) int {
initStatus(n)
dp[0][0] = 1
for i := 1; i <= m; i++ {
for j := 0; j < 1 << n; j++ {
dp[i][j] = 0
for k := 0; k < 1 << n; k++ {
if j & k == 0 && st[j | k] {
dp[i][j] += dp[i - 1][k]
}
}
}
}
return dp[m][0] // 最后一列
}
func main() {
var n, m int
for {
fmt.Fscan(reader, &n, &m)
if n | m == 0 { break }
fmt.Fprintln(writer, cal(n, m))
}
writer.Flush()
}