글 읽기 - [1992 쿼드트리] 반례 찾기 도와주세요 ㅠㅠ (boundary 체크)

alphago159 4년 전 0

쿼드 트리를 푸는 중 질문 게시판의 테스트 케이스와 N=1, N=64일때의 테스트 케이스를 만들어 테스트 해보았지만,

틀렸습니다로 나옵니다.

코드가 잘못되었을 수 있다고 생각합니다.ㅠㅠ

도와주세요

#include <iostream>

using namespace std;

void init();
int isSameColor(int **, int);
int ***divideGraph(int **partitionGraph, int n);
void quadTree(int **partitionGraph, int n);

int **graph;
int N;

int main() {

    init();

    if (isSameColor(graph, N) == -1)
        quadTree(graph, N);


    free(graph);
    return 0;
}

void init() {
    char num;
    scanf("%d%*c", &N);

    graph = new int *[N];
    for (int i = 0; i < N; i++) {
        graph[i] = new int[N];
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%c", &num);
            graph[i][j] = num - '0';
        }
        scanf("%*c");
    }
}

void quadTree(int **partitionGraph, int n) {

    int ***subGraph;
    int **LU, **RU, **LD, **RD;

    printf("(");

    subGraph = divideGraph(partitionGraph, n);

    LU = subGraph[0];
    if (isSameColor(LU, n / 2) == -1) {
        quadTree(LU, n / 2);
    }

    RU = subGraph[1];
    if (isSameColor(RU, n / 2) == -1) {
        quadTree(RU, n / 2);
    }

    LD = subGraph[2];
    if (isSameColor(LD, n / 2) == -1) {
        quadTree(LD, n / 2);
    }

    RD = subGraph[3];
    if (isSameColor(RD, n / 2) == -1) {
        quadTree(RD, n / 2);
    }

    printf(")");
}

int isSameColor(int **partitionGraph, int n) {
//같은 색이면 0 or 1 return, 다르면 -1

    int color = partitionGraph[0][0];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (color != partitionGraph[i][j]) {
                return -1;
            }
        }
    }

    printf("%d", color);
    return color;
}

int ***divideGraph(int **partitionGraph, int n) {
    int ***subGraph;
    int halfN = n / 2;
    subGraph = new int **[4]; //LU RU LD RD


    //Allocation
    for (int i = 0; i < 4; i++) {
        subGraph[i] = new int *[halfN];
        for (int j = 0; j < halfN; j++) {
            subGraph[i][j] = new int[halfN];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {

            if (i < halfN && j < halfN) {
                subGraph[0][i][j] = partitionGraph[i][j];
            }

            if (i < halfN && j >= halfN) {
                subGraph[1][i][j - halfN] = partitionGraph[i][j];
            }

            if (i >= halfN && j < halfN) {
                subGraph[2][i - halfN][j] = partitionGraph[i][j];
            }

            if (i >= halfN && j >= halfN) {
                subGraph[3][i - halfN][j - halfN] = partitionGraph[i][j];
            }
        }
    }

    return subGraph;
}

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

문제

문제

출처

ICPC

[1992 쿼드트리] 반례 찾기 도와주세요 ㅠㅠ (boundary 체크)

alphago159 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말