思路：

状态压缩dp。

实现：

1 #include 
     
       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 }