POJ1321 – JAVA編程語言程序開發技術文章

[java] 
package Search; 
 
import java.util.*; 
public class POJ1321 { 
 
    static int c;//結果 
    static int n,k; 
    static boolean[][] map;//用數組來標記地圖形狀 
    static boolean[] used;//標記器 
     
    public static void main(String[] args) { 
        Scanner sc = new Scanner(System.in); 
         
        while(sc.hasNext()){ 
            c = 0; 
            n = sc.nextInt(); 
            k = sc.nextInt(); 
             
            if(n==-1 && k==-1)return; 
             
            map = new boolean[n+1][n+1]; 
            used = new boolean[n+1]; 
             
            for(int i = 1; i<=n;i++){ 
                String temp = sc.next(); 
                for(int j = 0;j<n;j++){ 
                    char ch = temp.charAt(j); 
                    if(ch=='#')map[i][j+1] = true; 
                } 
            } 
            dfs(1,0);//從第一行開始搜索，開始的時候搜索到的棋子為0，註意這裡的初始值。 
            System.out.println(c); 
        } 
 
    } 
     //逐行搜索，row為當前搜索行，num為已填充的棋子數   
    private static void dfs(int row, int num) { 
        if(num == k){//如果填充的棋子滿瞭，表示搜索結束 
            c++; 
            return; 
        } 
        if(row>n)return;//搜索越界，搜索結束 
         
        for(int i = 1;i<=n;i++){ 
            if(map[row][i] && !used[i]){ 
                used [i] = true;//標記該行已經放置棋子 
                dfs(row+1,num+1); 
                 
                used [i] = false;//回溯 
            } 
        } 
         
        dfs(row+1,num);//這裡是難點，當k<n時，row在等於n之前就可能已經把全部棋子放好    
                       //又由於當全部棋子都放好後的某個棋盤狀態已經在前面循環時記錄瞭    
                      //因此為瞭處理多餘行，令當前位置先不放棋子，搜索在下一行放棋子的情況    
 
        return; 
         
    } 
 
}