题目链接：https://vjudge.net/problem/POJ-1321
Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
Input
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。
Output
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。
Sample Input
2 1 #. .# 4 4 ...# ..#. .#.. #... -1 -1Sample Output
2 1题解：利用DFS及回溯思想，从第一行开始放，并记录棋子的列的位置，具体实现见代码。
Cpp Code #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> using namespace std; const int maxn = 10; char G[maxn][maxn];//存储棋盘 bool vis[maxn];//记录第j列是否已放棋子 int n, k,ans=0; bool ok(int x,int y){ if(G[x][y]=='#'&&vis[y]==0){ return 1;//如果可以放棋子，返回1 } return 0; } void DFS(int step,int sum){ if(sum==k){ ans++;//已放满k个棋子，ans+1 return; } //DFS for (int i = step; i < n;i++){ for (int j = 0; j < n;j++){ if(ok(i,j)){ vis[j] = 1; DFS(i + 1, sum + 1); vis[j] = 0; } } } } int main(){ while (scanf("%d %d",&n,&k)==2&&!(n==-1&&k==-1)) { //初始化 memset(vis, 0, sizeof(vis)); ans = 0; for (int i = 0; i < n;i++){ for (int j = 0; j < n;j++){ cin >> G[i][j]; } } DFS(0, 0); cout << ans << endl; } return 0; } Java Code package Vj; import java.util.*; public class POJ1321 { static int maxn=10; static char[][] mp=new char[maxn][maxn];//存储棋盘 static boolean vis[]=new boolean[maxn];//记录第j列是否已放棋子 static int n,k; static Scanner sc=new Scanner(System.in); static int ans=0;//方案数量 static boolean ok(int x,int y) { if(mp[x][y]=='#'&&vis[y]==false) { return true;//如果可以放棋子，返回true } return false; } static void DFS(int step,int sum) { if(sum==k) { ans++;//可以放满看k个，ans+1 return; } //进行DFS for(int i=step;i<n;i++) { for(int j=0;j<n;j++) { if(ok(i,j)) { vis[j]=true; DFS(i+1,sum+1); vis[j]=false; } } } } public static void main(String[] args) { while((n=sc.nextInt())!=-1&&(k=sc.nextInt())!=-1) { for(int i=0;i<n;i++) { mp[i]=sc.next().toCharArray(); } ans=0; for(int i=0;i<10;i++) { vis[i]=false; } DFS(0,0); System.out.println(ans); } } }