rook

mail@pastecode.io avatar
unknown
c_cpp
5 days ago
1.1 kB
1
Indexable
Never
#include <iostream>

using namespace std;

int n, a[4][4];
int countRook, maxRook;

void input() {
	cin >> n;
	countRook = 0;
	maxRook = 0;
	char x[10];
	for (int i = 0; i < n; i++) {
		cin >> x;
		for (int j = 0; j < n; j++) {
			if (x[j] == '.') {
				a[i][j] = 0;
			}
			else {
				a[i][j] = 1;
			}
		}
	}
}

bool isSafe(int row, int col) {
	if (a[row][col] == 1) return false;

	for (int i = col; i >= 0; i--) {
		if (a[row][i] == 1) break;
		if (a[row][i] == 2) return false;
	}

	for (int i = row; i >= 0; i--) {
		if (a[i][col] == 1) break;
		if (a[i][col] == 2) return false;
	}

	return true;
}

void solve(int pos) {
	if (pos == n * n) {
		maxRook = max(maxRook,countRook);
		return;
	}
	int row = pos / n;
	int col = pos % n;
	if (isSafe(row, col)) {
		countRook++;
		a[row][col] = 2;
		solve(pos + 1);
		countRook--;
		a[row][col] = 0;
	}
	solve(pos + 1);
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		input();
		solve(0);
		cout << "Case #" << tc << endl;
		cout << maxRook << endl;
	}
	return 0;
}
Leave a Comment