Untitled

 avatar
user_1164828
plain_text
a month ago
1.1 kB
0
Indexable
Never
//Chess rook
//c++

#include<iostream>
using namespace std;

char map[6][6];
int visited[6][6];
int n;
int cntR;
int ans;
int cnt;

bool check(int r, int c){
	if(map[r][c] == 'X'){
		return false;

	}
	for(int i=r-1; i>=0; i--){
		if(map[i][c] == 'R') return false;
		else if(map[i][c] == 'X') break;
	}
	for(int i =c-1; i>=0; i--){
		if(map[r][i] == 'R'){
			return false;
		}
		else if(map[r][i] == 'X'){
			break;
		}
	}
	return true;
}

int _max(int x, int y){
	return (x > y) ? x : y;
}

void BT(int k, int cnt){
	if(k==n*n){
		ans = _max(ans,cnt);
		return;
	}
 	for(int i=0; i<2; i++){
		if(i==1 && check(k/n,k%n)){
			map[k/n][k%n] = 'R';
			BT(k+1,cnt+1);
			map[k/n][k%n] = '.';
		}
		else if (i == 0){
			BT(k+1, cnt);
		}
	}
}

int main(){
	//freopen ("Text.txt", "r", stdin);
	int T;
	cin>> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> n;
		for(int i=0; i<n; i++){
			cin >> map[i];
			for(int j=0; j< n; j++){
				visited[i][j] = 0;
				if(map[i][j] == 'X'){
					visited[i][j] = -1;
				}
			}
		}
		ans = 0;
		cnt = 0;
		BT(0,0);
		cout<< "Case #" << tc << endl << ans << endl;
	}
	return 0;
}
Leave a Comment