1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 int dp[13][1 << 12], mod = 1e8, state[13];15 16 int main()17 {18     int n, m;19     while(~scanf("%d %d", &n, &m)) {20         int num;21         for(int i = 1; i <= n; ++i) {22             state[i] = 0;23             for(int j = 1; j <= m; ++j) {24                 scanf("%d", &num);25                 state[i] = (state[i] << 1) + num; // 初始可行状态26             }27         }28         memset(dp, 0, sizeof(dp));29         for(int i = 0; i < (1 << m); ++i) { // 初始化第一行30             if((i & (i << 1)) == 0 && (i & state[1]) == i) { // 相邻没菜 且在可行状态中31                 dp[1][i] = 1;32             }33         }34         for(int i = 2; i <= n; ++i) {35             for(int j = 0; j < (1 << m); ++j) {36                 if((j & (j << 1)) == 0 && (j & state[i]) == j) {37                     for(int k = 0; k < (1 << m); ++k) {38                         if((j & k) == 0 && (k & state[i - 1]) == k) { //上下行菜不相邻 且上行可行39                             dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;40                         }41                     }42                 }43             }44         }45         int ans = 0;46         for(int i = 0; i < (1 << m); ++i) {47             ans = (dp[n][i] + ans) % mod;48         }49         printf("%d\n", ans);50     }51     return 0;52 }