Untitled

mail@pastecode.io avatarunknown
plain_text
2 months ago
1.1 kB
5
Indexable
Never
#include <iostream>
#define MAX 99999999
using namespace std;

int n;
char board[5][5];
int ans;

bool check(int x, int y){
	for(int i=x; i<n; i++){
		if(board[i][y]=='#')
			return false;
		if(board[i][y]=='X')
			break;
	}

	for(int i=x-1; i>=0; i--){
		if(board[i][y]=='#')
			return false;
		if(board[i][y]=='X')
			break;
	}

	for(int i=y; i<n; i++){
		if(board[x][i]=='#')
			return false;
		if(board[x][i]=='X')
			break;
	}

	for(int i=y-1; i>=0; i--){
		if(board[x][i]=='#')
			return false;
		if(board[x][i]=='X')
			break;
	}
	return true;
}

void backTrack(int num){
	ans = max(ans, num);
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(board[i][j]=='.' && check(i, j)){
				board[i][j]='#';
				backTrack( num+1);
				board[i][j]='.';
			}
		}
	}
}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> n;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				cin >> board[i][j];
			}
		}

		ans=0;

		backTrack( 0);

		cout << "Case #" << tc << endl;
		cout << ans << endl;
	}
	return 0;
}