[백준 1799번] 비숍

소스코드

---

#include <iostream>
using namespace std;
 
int n, board[11][11], Max = 0, visit[21] = { 0, }, visit_1[21] = { 0, };
 
void white(int a, int b, int cnt) {
    if (cnt > Max)
        Max = cnt;
 
    if (b >= n) {
        a++;
        if (a % 2 == 0)
            b = 0;
        else
            b = 1;
    }
 
    if (a >= n)
        return;
 
    if (visit[a + b] == 0 && board[a][b] == 1 && visit_1[10+a-b]==0) {
        visit[a + b] = 1;
        visit_1[10 + a - b] = 1;
        white(a, b+2, cnt + 1);
        visit[a + b] = 0;
        visit_1[10 + a - b] = 0;
    }
    white(a, b + 2, cnt);
}
 
void black(int a, int b, int cnt) {
    if (cnt > Max)
        Max = cnt;
 
    if (b >= n) {
        a++;
        if (a % 2 == 0)
            b = 1;
        else
            b = 0;
    }
 
    if (a >= n)
        return;
 
    if (visit[a + b] == 0 && board[a][b] == 1 && visit_1[10 + a - b] == 0) {
        visit[a + b] = 1;
        visit_1[10 + a - b] = 1;
        black(a, b + 2, cnt + 1);
        visit[a + b] = 0;
        visit_1[10 + a - b] = 0;
    }
    black(a, b + 2, cnt);
}
 
int main() {
    int sum = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    
    white(0, 0, 0);
    sum = Max;
    Max = 0;
    black(0, 1, 0);
    sum += Max;
    cout << sum << '\n';
    return 0;
}