글 읽기 - c++ 1799번 비숍 질문

yohanroh 3년 전 1

체스판처럼 칸을 나누어 각각 DFS 알고리즘으로 계산했지만 틀렸습니다. 왜 틀렸는지 알려주시면 감사하겠습니다.

#include <iostream>

using namespace std;

int n, ans1, ans2;
int arr[100][100];
int diag1[100];
int diag2[100];

void bis1(int x, int y, int cnt)
{
    if (y >= n) {
        if (cnt > ans1) ans1 = cnt;
        return;
    }
    if (x >= n){
        bis1(x % n, y + 1, cnt);
        return;
    }
    if (arr[x][y] == 1) {
        if (!diag1[x + y] && !diag2[x - y + n]) {
            diag1[x + y] = 1;
            diag2[x - y + n] = 1;
            bis1(x + 1, y, cnt + 1);
            diag1[x + y] = 0;
            diag2[x - y + n] = 0;
        }
    }
    bis1(x + 1, y, cnt);
}

void bis2(int x, int y, int cnt)
{
    if (y >= n) {
        if (cnt > ans2) ans2 = cnt;
        return;
    }
    if (x >= n) {
        bis2(x % n, y + 1, cnt);
        return;
    }
    if (arr[x][y] == 2) {
        if (!diag1[x + y] && !diag2[x - y + n]) {
            diag1[x + y] = 1;
            diag2[x - y + n] = 1;
            bis2(x + 1, y, cnt + 1);
            diag1[x + y] = 0;
            diag2[x - y + n] = 0;
        }
    }
    bis2(x + 1, y, cnt);
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if ((n * i + j) % 2 && arr[i][j]) arr[i][j] = 2;
        }
    }
    bis1(0, 0, 0);
    bis2(0, 0, 0);
    cout << ans1 + ans2 << endl;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 1799번 비숍 질문

yohanroh 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말