题意
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,求方法数
分析
相当于对棋盘的每一个可放点开始往后枚举,一个有效的剪枝是
每次搜索第num个棋子可选择的位置时,只用搜从当前行的下一行到n-(num-1)之间的行,找第num个棋子放的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include <string> #include <cstring> #include <cstdio> #include <iostream> using namespace std; int n,k,sum; char m[10][10]; int c[10],r[10]; void dfs(int num,int x){ if(num==0){ sum++; cout<<m[i]<<endl; } cout<<endl;*/ return; } for(int i=x+1;i<n-num+1;i++){ for(int j=0;j<n;j++){ if(m[i][j]=='#'&&c[j]==0&&r[i]==0){ m[i][j]='.'; c[j]=1; r[i]=1; dfs(num-1,x+1); m[i][j]='#'; c[j]=0; r[i]=0; } } } return; } int main() { while(scanf("%d%d",&n,&k)!=EOF){ if(n==-1&&k==-1){ break; } memset(c,0,sizeof(c)); memset(r,0,sizeof(r)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf(" %c",&m[i][j]); } } sum=0; dfs(k,-1); printf("%d\n",sum); } return 0; }
|