$n\times m$ 的矩阵，满足 $n,m\le 15$，每个格子有限制，$0$ 为可选， $1$ 为不可选。相邻格子不能同时选择。求选择格子的方案数。

如果设计 $f_{i,s}$ 表示为状态标识计算到第 $i$ 行，上一行为 $s$，这样复杂度为 $O(n\times2^{2n})$ 不可做。