백준 1799번 C++ 풀이

시간초과의 엄청난 고통..

#include <iostream>
#include <algorithm>
#include <queue>
#include <math.h>
#include <climits>
#include <map>
using namespace std;
int n;

int buffer[10][10];

int maxBishop[2];
bool isPlaceable(int,int);
void dfs(int x, int y, int currentBishop, int color){
    if (x >= n){

        if (x % 2 == 0) x=1;
        else x=0;
        y++;
    }
    while (y < n){
//        cout << x << ' ' << y << ' ' << currentBishop<< '\n';

        if (buffer[x][y] == 1){

            if (isPlaceable(x, y)){
                buffer[x][y] = 2;
                maxBishop[color] = max(maxBishop[color], currentBishop+1);
                dfs(x+2, y, currentBishop+1,color);
                buffer[x][y] = 1;
            }

        }
        x= x+2;
        if (x >= n){
            if (x % 2 == 0) x=1;
            else x=0;
            y++;
        }
    }

}
//            buffer[x][y] = 2;
////                cout << i << ' ' << j << ' ' << currentBishop<< '\n';
//            queue<pair<int, int>> q;
//            for (int start_x = x+1,  start_y = y+1; start_x<n && start_y <n; start_x++, start_y++ ){
//                if (buffer[start_x][start_y] == 1){
//                    buffer[start_x][start_y] = 2;
//                    q.push(make_pair(start_x, start_y));
//                }
//            }
////            for (int start_x = x-1,  start_y = y-1; start_x>=0 && start_y >=0; start_x--, start_y-- ){
////                if (buffer[start_x][start_y] == 1){
////                    buffer[start_x][start_y] = 2;
////
////                    q.push(make_pair(start_x, start_y));
////                }
////            }
//            for (int start_x = x+1, start_y = y-1; start_x < n && start_y >= 0; start_x++, start_y--){
//                if (buffer[start_x][start_y] == 1){
//                    buffer[start_x][start_y] = 2;
//
//                    q.push(make_pair(start_x, start_y));
//                }
//            }
//
//            for (int start_x = x-1, start_y = y+1; start_x >= 0 && start_y < n; start_x--, start_y++){
//                if (buffer[start_x][start_y] == 1){
//                    buffer[start_x][start_y] = 2;
//
//                    q.push(make_pair(start_x, start_y));
//                }
//            }
//
//            maxBishop[color] = max(maxBishop[color], currentBishop+1);
//            dfs(index+2, currentBishop+1,color);
//            while (!q.empty()){
//                buffer[q.front().first][q.front().second] = 1;
//                q.pop();
//            }
//            buffer[x][y] = 1;
bool isPlaceable(int x, int y){
//    if (x > y){
//        for (int start_x = x-y,  start_y = 0; start_x<n; start_x++, start_y++ ){
//            if (start_x != x && buffer[start_x][start_y] == 2){
//                return false;
//            }
//        }
//    }else {
//        for (int start_x = 0,  start_y = y-x; start_y<n; start_x++, start_y++ ){
//            if (start_x != x && buffer[start_x][start_y] == 2){
//                return false;
//            }
//        }
//    }
//    for (int start_x = x+1, start_y = y-1; start_x < n && start_y >= 0; start_x++, start_y--){
//        if (buffer[start_x][start_y] == 2){
//            return false;
//        }
//    }
//    for (int start_x = x-1, start_y = y+1; start_x >= 0 && start_y < n; start_x--, start_y++){
//        if (buffer[start_x][start_y] == 2){
//            return false;
//        }
//    }
    for (int start_x = x+1,  start_y = y+1; start_x<n && start_y <n; start_x++, start_y++ ){
        if (buffer[start_x][start_y] == 2){
            return false;
        }
    }
    for (int start_x = x-1,  start_y = y-1; start_x>=0 && start_y >=0; start_x--, start_y-- ){
        if (buffer[start_x][start_y] == 2){
            return false;
        }
    }
    for (int start_x = x+1, start_y = y-1; start_x < n && start_y >= 0; start_x++, start_y--){
        if (buffer[start_x][start_y] == 2){
            return false;
        }
    }

    for (int start_x = x-1, start_y = y+1; start_x >= 0 && start_y < n; start_x--, start_y++){
        if (buffer[start_x][start_y] == 2){
            return false;
        }
    }
        return true;
}
int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    for(auto i=0; i<n; i++){
        for (auto j=0; j<n; j++){
            cin >> buffer[i][j];
        }
    }
    dfs(0,0,0,0);
    dfs(1,0,0,1);

    cout << maxBishop[0]+maxBishop[1];

    return 0;
}