思路:dp

dp[i][j]表示经过(i, j) 这个点的方案数

然后一层一层地转移, 对于某一层, 用二进制枚举这一层的连接情况,

判断连接是否符合题意, 然后再进行转移

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
     
      using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
      
       #define pli pair
       
        #define pii pair
        
         #define piii pair
         
          #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 105, M = 8;const int MOD = 1e9 + 7;int dp[N][M];int main() {    int h, w, k;    scanf("%d %d %d", &h, &w, &k);    if(w == 1) return 0*puts("1");    dp[0][0] = 1;    for (int i = 1; i <= h; i++) {        for (int k = 0; k < 1<<(w-1); k++) {            bool f = true;            for (int j = 0; j < (w-2); j++) {                if((k&(1<
          
           = 1 && (k&(1<