题目大意：给一个N*N的区域，和M个棋子，询问最后有多少种摆的方法，其中每个棋子不能放在同一行和同一列。
思路：对每一行进行dfs，dfs时使用book数组（双重标记）标记。
#include<stdio.h> #include<string.h> #define N 9 char z[N][N];//开空间存储棋盘 int num;//计算总数 int bookh[N];//标记横行是否有过棋子 int bookl[N];//标记纵行是否有过棋子 int n,k; void dfs(int a,int m); int main(void) { while(scanf("%d%d",&n,&k),n!=-1){ memset(bookh,0,sizeof(bookh)); memset(bookl,0,sizeof(bookl)); num=0; getchar(); int i; for(i=0;i<n;i++) gets(z[i]); for(i=0;i<=n-k;i++){//优化，因为只有前n-k行，才能存下k个棋子 dfs(i,k);//dfs每一行 } printf("%d\n",num); } return 0; } void dfs(int a,int m){ if(m==0) { // num++; return ; } int i; for(i=0;i<n;i++){ if(z[a][i]=='#'&&bookh[a]==0&&bookl[i]==0){//找到这一列中可以放置棋子的点 if(m==1) { num++; // return ; } bookh[a]=1; bookl[i]=1; int j; for(j=a+1;j<=n-m+1;j++){//寻找下一行来放置棋子 dfs(j,m-1); } bookh[a]=0; bookl[i]=0; } } return ; }