Untitled

package APS2;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class ChessRook {
	static int N;
	static int[][] board;
	static int maxRook;

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src\\APS2\\ChessRook_input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			board = new int[N][N];
			for (int i = 0; i < N; i++) {
				String line = sc.next();
				for (int j = 0; j < N; j++) {
					if (line.charAt(j) == 'X') {
						board[i][j] = 1; // o co tuong
					}
				}
			}
			maxRook = 0;
			Solve(0, 0);
			System.out.println("Case #" + tc);
			System.out.println(maxRook);

		} // for tc
	}

	public static void Solve(int row, int countRook) {
		if (countRook > maxRook) {
			maxRook = countRook;
			// return;
		}

		for (int i = row; i < board.length; i++) { // dat rook theo hang
			for (int j = 0; j < board[0].length; j++) {
				if (isSafe(i, j)) {
					board[i][j] = 2; // dat xe = 2
					Solve(i, countRook + 1);
					board[i][j] = 0;
				}
			}
		}
	}

	static boolean isSafe(int row, int col) {
		if (board[row][col] == 1 || board[row][col] == 2) { // la tuong hoc da
															// co xe
			return false;
		}

		// cung cot, hang ben tren
		for (int i = row; i >= 0; i--) {
			if (board[i][col] == 2) { // gap xe truoc -> false
				return false;
			} else if (board[i][col] == 1) { // gap tuong, break de xet tiep cac
												// dieu kien sau, co kha nang
												// thoa man
				break;
			}
		}

		// cung hang, cot ben trai
		for (int i = col; i >= 0; i--) {
			if (board[row][i] == 2) {
				return false;
			} else if (board[row][i] == 1) {
				break;
			}
		}
		// cung hang, cot ben phai
		for (int i = col; i < board[0].length; i++) {
			if (board[row][i] == 2) {
				return false;
			} else if (board[row][i] == 1) {
				break;
			}
		}
		return true;
	}
}