程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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; 
                } 
            } 
        } 
    } 

 作者:lhfight


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved