题目链接： 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 ", ans); 73 return 0; 74 }