1799 비숍

1799 비숍

개인적으로 정말 어려웠다.

처음 N-Queens Problem풀듯이 풀려고 했으나 시간초과가 났고 대각탐색등 다양하게 해봤는데 다 실패했다. 다음방법으로 검정칸에 있는 비숍은 검정칸만 이동가능하고 하얀칸에 있는 비숍은 하얀칸만 이동 가능하므로 맵을 반으로 나눠 각각 백트래킹 하였다.

dfs은 하얀칸만 탐색/ dfs2는 검정칸만 탐색 하도록 하였다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int n, res, cnt;
int map[10][10];
bool visited[10][10];
 
//타탕성 검증
bool isOK(int r,int c) {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < n; j++) {
            if (visited[i][j]) {
                if (abs(r - i) == abs(c - j))return false;
            }
        }
    }
    return true;
}
 
void printAll() {
    cout << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (visited[i][j]) cout << "o ";
            else cout << "x ";
        }
        cout << endl;
    }
}
 
void dfs(int x,int y) {
    if (!isOK(x, y)) return;
 
    visited[x][y] = true;
    cnt++;
    if (res < cnt) {
        res = cnt;
    }
    for (int i = y + 1; i < n; i++) {
        if (x % 2 == 0) {
            if (i % 2 == 0) {
                if (map[x][i] == 1)
                    dfs(x, i);
            }
        }
        if (x % 2 == 1) {
            if (i % 2 == 1) {
                if (map[x][i] == 1)
                    dfs(x, i);
            }
        }
    }
    for (int i = x + 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i % 2 == 0) {
                if (j % 2 == 0) {
                    if (map[i][j] == 1)
                        dfs(i, j);
                }
            }
            if (i % 2 == 1) {
                if (j % 2 == 1) {
                    if (map[i][j] == 1)
                        dfs(i, j);
                }
            }
        }
    }
 
    cnt--;
    visited[x][y] = false;
}
 
void dfs2(int x, int y) {
    if (!isOK(x, y)) return;
 
    visited[x][y] = true;
    cnt++;
    if (res < cnt) {
        res = cnt;
    }
    for (int i = y + 1; i < n; i++) {
        if (x % 2 == 0) {
            if (i % 2 == 1) {
                if (map[x][i] == 1)
                    dfs2(x, i);
            }
        }
        if (x % 2 == 1) {
            if (i % 2 == 0) {
                if(map[x][i] == 1)
                    dfs2(x, i);
            }
        }
    }
    for (int i = x + 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i % 2 == 0) {
                if (j % 2 == 1) {
                    if (map[i][j] == 1)
                        dfs2(i, j);
                }
            }
            if (i % 2 == 1) {
                if (j % 2 == 0) {
                    if (map[i][j] == 1)
                        dfs2(i, j);
                }
            }
        }
    }
 
    cnt--;
    visited[x][y] = false;
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
    int ans = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i % 2 == 0) {
                if (j % 2 == 0) {
                    if (map[i][j] == 1)
                        dfs(i, j);
                }
            }
            if (i % 2 == 1) {
                if (j % 2 == 1) {
                    if (map[i][j] == 1)
                        dfs(i, j);
                }
            }
        }
    }
    ans += res;
    res = 0;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i % 2 == 0) {
                if (j % 2 == 1) {
                    if (map[i][j] == 1)
                        dfs2(i, j);
                }
            }
            if (i % 2 == 1) {
                if (j % 2 == 0) {
                    if (map[i][j] == 1)
                        dfs2(i, j);
                }
            }
        }
    }
    ans += res;
 
    cout << ans << endl;
}