chessboard.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;
import java.util.Scanner;


/**
 * ID:1321
 * DFS
 * @author yhm
 *
 */
public class Chessboard {
	
	static int blank = -1;
	static int board = 0;
	static int inUse = 1;
	
	static int size;
	static int result;
	static int[][] chess;
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			size = cin.nextInt();
			int k = cin.nextInt();
			if(size==-1&&k==-1){
				break;
			}
			chess = new int[size][size];
			for(int i=0;i<size;i++){
				String str = cin.next();
				for(int j=0;j<size;j++){
					if(str.charAt(j) == '#'){
						chess[i][j] = board;
					}
					else{
						chess[i][j] = blank;
					}
				}
			}
			result=0;
			if(k>size){
				System.out.println(0);
			}
			else{
				for(int i=0;i<=size-k;i++){
					DFS(i,k);
				}
				System.out.println(result);
			}
			
		}

	}
	
	static boolean check(int row, int col){
		if(chess[row][col] == blank){
			return false;
		}
		for(int i=0;i<size;i++){
			if(chess[row][i] == inUse || chess[i][col] == inUse){
				return false;
			}
		}
		return true;
	}
	
	static void DFS(int row, int k){
		if(k==0){
			result++;
			return;
		}
		if(row==size){
			return;
		}
		for(int col=0;col<size;col++){
			if(check(row, col)){
				chess[row][col] = inUse;
				if(k-1==0){
					result++;
				}
				else{
					for(int i=row+1;i<=size-k+1;i++){
						DFS(i,k-1);
					}
				}

				
				chess[row][col] = board;
			}
		}
	}

}