Untitled

mail@pastecode.io avatar
unknown
plain_text
18 days ago
1.3 kB
2
Indexable
Never
#include<iostream>
using namespace std;
int t,n, ans;
char mang[5][5];
bool check[5][5];

bool checkHang(int a, int b){
	for(int i=b+1; i<n; i++){
		if(mang[a][i]=='X')
			break;
		else{
			if(check[a][i]==false)
				return false;
		}
	}
	for(int i=b-1; i>=0; i--){
		if(mang[a][i]=='X')
			break;
		else{
			if(check[a][i]==false)
				return false;
		}
	}
	return true;
}
bool checkCot(int a, int b){
	for(int i=a+1; i<n; i++){
		if(mang[i][b]=='X')
			break;
		else{
			if(check[i][b]==false)
				return false;
		}
	}
	for(int i=a-1; i>=0; i--){
		if(mang[i][b]=='X')
			break;
		else{
			if(check[i][b]==false)
				return false;
		}
	}
	return true;
}
void bt(int dem){
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(mang[i][j]=='.' && checkHang(i,j) && checkCot(i,j) && check[i][j]){
				check[i][j]=false;
				bt(dem+1);
				check[i][j]=true;
			}
			if(i==n-1 && j==n-1){
				if(dem>ans)
					ans=dem;
				break;
			}
		}
	}
}

int main(){
	freopen("Text.txt", "r", stdin);
	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++){
				check[i][j]=true;
				cin >> mang[i][j];
			}
		}
		ans=0;
		bt(0);
		cout << "Case #" << tc << endl;
		cout << ans << endl;
	}
	return 0;
}
Leave a Comment