http://poj.org/problem?id=1321
注意是在'#'的地方放棋子
矩阵大小不过8*8,即使是8!的时间复杂度也足以承受,可以直接dfs求解
dfs时标注当前点的行和列已被访问,接着搜索行列都未被访问的新点,注意搜索完毕之后标注当前点的行和列未被访问
#include <cstdio>
#include <cstring>
using namespace std;
int n,k;
char maz[8][9];
int e[8][8],len[8];
bool r[8],c[8];
void dye(int x,int y){
r[x]=c[y]=true;
}
void undye(int x,int y){
r[x]=c[y]=false;
}
int dfs(int s,int cnt){
if(cnt<=0)return 1;
int ans=0;
for(int i=s+1;cnt+i<=n;i++){
for(int j=0;j<len[i];j++){
if(r[i]||c[e[i][j]])continue;
dye(i,e[i][j]);
ans+=dfs(i,cnt-1);
undye(i,e[i][j]);
}
}
return ans;
}
int main(){
while(scanf("%d%d",&n,&k)==2&&n!=-1){
for(int i=0;i<n;i++)scanf("%s",maz[i]);
memset(len,0,sizeof(len));
memset(r,0,sizeof(r));
memset(c,0,sizeof(c));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(maz[i][j]=='#'){
e[i][len[i]++]=j;
}
}
}
if(k==0){
puts("0");
continue;
}
int ans=0;
for(int i=0;k+i<=n;i++){
for(int j=0;j<len[i];j++){
dye(i,e[i][j]);
ans+=dfs(i,k-1);
undye(i,e[i][j]);
}
}
printf("%d\n",ans);
}
return 0;
}