网上代码1:
#include<stdio.h> #include<string.h> int n,k,vis[15],ans; char mat[15][15]; void dfs(int cur,int num) { if(num==k) { ans++; return; } for(int i=cur;i<n;i++) for(int j=0;j<n;j++) if(mat[i][j]=='#' && !vis[j]) { vis[j]=1; dfs(i+1,num+1); vis[j]=0; } } int main() { while(~scanf("%d %d%*c",&n,&k) && n!=-1 && k!=-1) { memset(vis,0,sizeof(vis)); int i; for(i=0;i<n;i++) gets(mat[i]); ans=0; dfs(0,0); printf("%d\n",ans); } return 0; }网站代码2: #include<iostream> #include<cstdio> #include<cstring> using namespace std; char a[10][10]; //记录棋盘位置 int book[10]; //记录一列是否已经放过棋子 int n,k; int total,m; //total 是放棋子的方案数 ，m是已放入棋盘的棋子数目 void DFS(int cur) { if(k==m) { total++; return ; } if(cur>=n) //边界 return ; for(int j=0; j<n; j++) if(book[j]==0 && a[cur][j]=='#') //判断条件 { book[j]=1; //标记 m++; DFS(cur+1); book[j]=0; //改回来方便下一行的判断 m--; } DFS(cur+1); //到下一行 } int main() { int i,j; while(scanf("%d%d",&n,&k)&&n!=-1&&k!=-1) //限制条件 { total=0; m=0; for(i=0; i<n; i++) scanf("%s",&a[i]); memset(book,0,sizeof(book)); DFS(0); printf("%d\n",total); } return 0; } my: #include <algorithm> #include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> using namespace std; char map[15][15]; int book[15]; int n, k; int ans; int m; void dfs(int cur) { if(m == k){ ans++; return ; } if(cur >= n) return; for(int j = 0;j < n;j++){ if(!book[j]&&map[cur][j]=='#'){ m++; book[j] = 1; dfs(cur+1); book[j] = 0; m--; } } dfs(cur+1); } int main() { while(~scanf("%d %d", &n, &k)){ if(n == -1 && k == -1) break; for(int i = 0;i < n;i++){ scanf("%s", map[i]); } m = 0; ans = 0; memset(book,0,sizeof(book)); dfs(0); printf("%d\n", ans); } return 0; }