程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> HDU1045

HDU1045

編輯：關於C語言

[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.2cto.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;
                    row[i] = 0;
                    colunm[j] = 0;
                }
                // 遇到牆時當前行和列又可以使用
                else if(ch[i][j]=='X'){
                    row[i] = 0;
                    colunm[j] = 0;
                }
            }
        }
    }
}