#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <stack> #include <queue> #include <algorithm> #include <string> const int inf = (1<<31)-1; const int MAXN = 1e1; using namespace std; int n,m; char G[MAXN][MAXN]; int row[MAXN],col[MAXN],num[MAXN]; int sum; void dfs(int x,int t){ if(t==m-1){ sum++; return ; } for(int i=x+1;i<n;i++){ if(num[i]+t>=m-1){//剪枝2 for(int j=0;j<n;j++){ if(!row[i]&&!col[j]&&G[i][j]=='#'){ row[i] = col[j] = 1; //cout<<i<<j<<"debug"<<endl; dfs(x+1,t+1); row[i] = col[j] = 0; } } } } } int main() { while(scanf("%d%d",&n,&m),n!=-1){ sum = 0; int k =0; memset(row,0,sizeof(row)); memset(col,0,sizeof(col)); memset(num,0,sizeof(num)); for(int i=0;i<n;i++){ scanf("%s",G[i]); } for(int i=n-1;i>=0;i--){ for(int j=0;j<n;j++){ if(G[i][j]=='#'){ num[i] = 1; k++; } } num[i] += num[i+1]; //每行下至少还有多少个 } //剪枝1 if(k<m||num[0]<m){ cout<<0<<endl; continue; } /* for(int i=0;i<n;i++){ printf("%s\n",G[i]); }*/ for(int i=0;i<n-m+1;i++){ if(num[i]>=m){ for(int j=0;j<n;j++){ if(G[i][j]=='#'){ row[i] = col[j] = 1; dfs(i,0); row[i] = col[j] = 0; } } }else{break;} } cout<<sum<<endl; } //cout << "Hello world!" << endl; return 0; } |
Double click to view unformatted code.