1799.cpp

#include <iostream>
#include <algorithm>
using namespace std;
int chess_size;
int map[11][11];
int max_black = 0, max_white = 0;
bool slash[22];
bool back_slash[22];

void black(int y, int x, int cnt) {
	max_black = max(max_black, cnt);

	if (x > chess_size) { //position이 체스의 끝부분에 도달하였을때,
		y++;
		x = (y % 2 == 0) ? 1 : 2;
	}
	if (y > chess_size) {
		return;
	}

	if (map[y][x] != 0 && slash[y + x] == false && back_slash[10 + (y - x)] == false) {
		slash[y + x] = true;
		back_slash[10 + (y - x)] = true;

		black(y, x + 2, cnt + 1);

		slash[y + x] = false;
		back_slash[10 + (y - x)] = false;
	}
	black(y, x + 2, cnt);
}

void white(int y, int x, int cnt) {
	max_white = max(max_white, cnt);

	if (x > chess_size) { //position이 체스의 끝부분에 도달하였을때,
		y++;
		x = (y % 2 == 0) ? 2 : 1;
	}
	if (y > chess_size) {
		return;
	}

	if (map[y][x] != 0 && slash[y + x] == false && back_slash[10 + (y - x)] == false) {
		slash[y + x] = true;
		back_slash[10 + (y - x)] = true;

		white(y, x + 2, cnt + 1);

		slash[y + x] = false;
		back_slash[10 + (y - x)] = false;
	}
	white(y, x + 2, cnt);
}
int main()
{
	cin >> chess_size;
	for (int i = 1; i <= chess_size; i++) {
		for (int j = 1; j <= chess_size; j++) {
			cin >> map[i][j];
		}
	}
	black(1, 2, 0);
	white(1, 1, 0);
	cout << max_black + max_white << "\n";
}