1799 bishop

์ฝ”๋“œ

#include <iostream>
#include <cstring>
#define MAX_N 10
 
using namespace std;
 
int map[MAX_N][MAX_N];
bool tempMap[MAX_N][MAX_N] = { 0, };
int width, maxCount = 0;
 
void findMaxBishop(int diagonal, int count);
bool check(int row, int col);
 
int main() {
	cin >> width;
	for (int i = 0; i < width; i++)
		for (int j = 0; j < width; j++)
			cin >> map[i][j];
	findMaxBishop(0, 0);
	cout << maxCount;
}
 
void findMaxBishop(int diagonal, int count) {
	if (diagonal == 2 * width - 1) {
		maxCount = maxCount > count ? maxCount : count;
		return;
	}
	if ((2 * (width - 1)) - diagonal < maxCount - count)
		return;
 
	int row = 0, col = 0;
	if (diagonal < width)
		col = diagonal;
	else {
		row = diagonal - width + 1;
		col = width-1;
	}
 
	for (; row < width && col >= 0; row++) {
		if (map[row][col] == 1 && check(row - 1, col - 1)) {
			tempMap[row][col] = true;
			findMaxBishop(diagonal + 1, count + 1);
			tempMap[row][col] = false;
		}
		col--;
	}
	findMaxBishop(diagonal + 1, count);
}
 
bool check(int row, int col) {
	for (; row >= 0 && col >= 0; row--)
		if (tempMap[row][col--])
			return false;
	return true;
}