Untitled

#include<iostream>
using namespace std;

char chess[5][5];
bool visited[5][5];
int nTestcase, N, cnt, maxCnt, x, y;
bool checkX, checkY;

void backtrack(int row , int col){
	if(row == N) {
		maxCnt = cnt > maxCnt ? cnt : maxCnt;
		return;
	}
	for(int i = col; i < N; i++){
		if(chess[row][i] == '.' && visited[row][i] == false){
			checkX = checkY = false;
			for(int j = 0; j < N; j++){
				if(visited[j][i] == true){
					checkY = true;
					if(row > j){
						for(int k = j + 1; k < row; k++){
							if(chess[k][i] == 'X') checkY = false;
						}
					} else{
						for(int k = row + 1; k < j; k++){
							if(chess[k][i] == 'X') checkY = false;
						}
					}
				}
				if(visited[row][j] == true){
					checkX = true;
					if(i > j){
						for(int k = j + 1; k < i; k++){
							if(chess[row][k] == 'X') checkX = false;
						}
					} else{
						for(int k = i + 1; k < j; k++){
							if(chess[row][k] == 'X') checkX = false;
						}
					}
				}
			}
		}
		if(checkX == false && checkY == false && chess[row][i] == '.'){
			visited[row][i] = true;
			cnt++;
			if(i < N - 1){
				backtrack(row, i + 1);
			}else{
				backtrack(row + 1, 0);
			}
			visited[row][i] = false;
			cnt--;
		}else{
			if(i < N - 1){
				backtrack(row, i + 1);
			}else{
				backtrack(row + 1, 0);
			}
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> nTestcase;
	for(int testcase = 1; testcase <= nTestcase; testcase++){
		cin >> N;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				cin >> chess[i][j];
				visited[i][j] = false;
			}
		}
		cnt = maxCnt = 0;
		backtrack(0,0);
		cout << "Case #" << testcase << endl << maxCnt << endl;
	}
	return 0;
}