HDU1045
[java]
package D0710;
//二分匹配(DFS/BFS/匈牙利算法的实现)
import java.util.Scanner;
public class HDU1045 {
static char[][] ch;// 保存开始的输入
static boolean used[][];// 这个格子是否被使用过
static int row[];// 行是否修筑了碉堡（修筑为1，未修筑为0）
static int colunm[];// 该列是否修筑了碉堡（修筑为1，未修筑为0）
static int count;// 最后的碉堡数（结果）
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n;
String[] arr; www.zzzyk.com
while (sc.hasNext()) {
count = 0;
n = sc.nextInt();
if (n == 0)
break;
arr = new String[n];
ch = new char[n][n];
row = new int[n];
colunm = new int[n];
used = new boolean[n][n];
for (int i = 0; i < n; i++) {
arr[i] = sc.next();
}
// 将输入的字符保存在一个字符数组中
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ch[i][j] = arr[i].charAt(j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (ch[i][j] == '.') {
//用掉当前格子，并设置该格子在此次循环中不再可用
used[i][j] = true;
row[i] = 1;
colunm[j] = 1;
dfs(1);
//下次循环时当前行可以和列可以继续使用
used[i][j] = false;
row[i] = 0;
colunm[j] = 0;
}
}
}
System.out.println(count);
}
}
// 二分匹配
private static void dfs(int cnt) {
if (cnt > count)
count = cnt;
int i,j;
for (i = 0; i <row.length; i++) {
for (j = 0; j <row.length; j++) {
// 当前格子没有被使用并且当前行和列没有修筑碉堡
if (ch[i][j] == '.' && !used[i][j] && row[i] == 0 && colunm[j] == 0) {
//用掉当前格子，并且使当前行和列在此次循环中不再可用
used[i][j] = true;
row[i] = 1;
colunm[j] = 1;
dfs(cnt+1);//在此格子修筑碉堡（碉堡数目+1）
//让当前行和列在下次循环使可以用
used[i][j] = false;
补充：软件开发 , C语言 ,
