hihocoder编程练习赛52-2 亮灯方案

思路：
状态压缩dp。
实现：
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int MAXN = 22;
 5 const int dx[4] = {0, 1, -1, 0};
 6 const int dy[4] = {1, 0, 0, -1};
 7 int n, m; 
 8 ll dp[(1 << 20) + 5];
 9 char a[MAXN][MAXN], tmp[MAXN][MAXN];
10 bool check(int x, int y, int S)
11 {
12     for (int i = 0; i < 4; i++)
13     {
14         int nx = x + dx[i], ny = y + dy[i];
15         if (nx >= 0 && nx < n && ny >= 0 && ny < m && (S & (1 << (nx * m + ny))))
16             return true;
17     }
18     return false;
19 }
20 ll dfs(int now, int S)
21 {
22     if (dp[S] != -1) return dp[S];
23     if (now == n * m) return 1;
24     ll cnt = 0;
25     for (int i = 0; i < n; i++)
26     {
27         for (int j = 0; j < m; j++)
28         {
29             int x = i * m + j;
30             if (!(S & (1 << x)) && check(i, j, S))
31                 cnt += dfs(now + 1, S | (1 << (i * m + j)));
32         }
33     }
34     return dp[S] = cnt;
35 }
36 
37 int main()
38 {
39     cin >> n >> m;
40     int now = 0, S = 0;
41     for (int i = 0; i < n; i++)
42         for (int j = 0; j < m; j++)
43             cin >> a[i][j];
44     for (int i = 0; i < n; i++)
45     {
46         for (int j = 0; j < m; j++)
47         {
48             if (a[i][j] == '1') 
49             {
50                 now++;
51                 S |= (1 << i * m + j);
52             }
53         }
54     }    
55     memset(dp, -1, sizeof dp);
56     cout << dfs(now, S) << endl;
57     return 0;
58 }