# Untitled

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;
}```