题目大意： 给定一个不规则的棋盘，往这个棋盘里摆放K个棋子，求棋子的最大摆放组合数。
这属于深度搜索历遍的题，不过与紫书上的求油田连通块不同的是，这道题要历遍n张图，由n行开始，有n-1，n-2，以此类推直到n-1。 由于行和列不能放多个棋子，我们可以巧妙地用一个一维数组vis来记录列的状态，用deep来生成多张图，接着就是dfs了，不过要注意的是，我们需要多次历遍，所以在dfs回溯到上一个状态时，vis[i]同样也要变回被调用前的状态。 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 8; int n,k; int t;//棋子摆放组合数 int vis[maxn];//列的状态 char dis[maxn][maxn]; void dfs(int deep = 0, int q = k)//deep用来定义新的图 { if(0 == q)//棋子用完时返回上一个状态 { t++; return ; } if(deep >= n)//所有地图历遍后结束dfs return; for(int j = deep; j < n; j++) { for(int i = 0; i < n; i++) { if(dis[j][i] == '#' && vis[i] != 1) { vis[i] = 1; dfs(j+1, q-1); vis[i] = 0;//回溯未调用前的状态 } } } } int main() { while(scanf("%d%d", &n, &k) && n != -1 && k != -1) { memset(vis, 0, sizeof(vis)); memset(dis, 0, sizeof(dis)); t = 0; for(int j = 0; j < n; j++) { cin >> dis[j]; } dfs(); cout << t << endl; } return 0; }