hihocoder_offer收割程式設計練習賽52_2亮燈方案

題目連結： https://hihocoder.com/contest/offers52/problem/2

解題思路： 題目中的關鍵限制條件是n*m<=20，是以總的狀态空間是2^20個。從初始狀态，依次枚舉每個可能的操作，統計方案總數。

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 char s[21];
 5 bool a[21][21];
 6 int n, m;
 7 map<int, long long> vis;
 8 long long ans;
 9 
10 int judge(int i, int j)
11 {
12     if (i - 1 >= 0 && a[i-1][j] == 1) return 1;
13     if (i + 1 < n && a[i+1][j] ==1 )return 1;
14     if (j-1 >= 0 && a[i][j-1] == 1) return 1;
15     if (j + 1 < m && a[i][j+1] == 1) return 1;
16     return 0;
17 }
18 
19 int array_to_int(bool a[21][21])
20 {
21     int res = 0;
22     for (int i = 0; i < n; ++i)
23     {
24         for (int j = 0; j < m; ++j)
25         {
26             res = res*2 + a[i][j];
27         }
28     }
29     return res;
30 }
31 
32 long long dfs(bool a[21][21])
33 {
34     int hasha = array_to_int(a);
35     if (vis.find(hasha) != vis.end())
36     {
37         return vis[hasha];
38     }
39     int flags = 0;
40     long long res = 0;
41     for (int k = 0; k < n*m; ++k)
42     {
43         int i = k / m;
44         int j = k % m;
45         if (a[i][j] == 0 && judge(i, j))
46         {
47             a[i][j] = 1;
48             res += dfs(a);
49             a[i][j] = 0;
50             flags = 1;
51         }
52     }
53     if (!flags)
54         res = 1;
55     vis[hasha] = res;
56     return res;
57 }
58 
59 
60 int main()
61 {
62     scanf("%d%d", &n, &m);
63     for (int i = 0; i < n; ++i)
64     {
65         scanf("%s", s);
66         for (int j = 0; j < m; ++j)
67         {
68             a[i][j] = (s[j]=='1'?1:0);
69         }
70     }
71     long long ans = dfs(a);
72     printf("%lld\n", ans);
73     return 0;
74 }      

轉載于:https://www.cnblogs.com/djingjing/p/8645345.html