쿼드 트리 알고리즘 문의 드립니다.

  • nwtest008
    nwtest008

    안녕하세요 쿼드 트리 뒤집기 알고리즘관련하여 문의드립니다.
    전체적인 알고리즘은 주어진 쿼드 트리 문자열을 find()재귀 함수로 읽어 직접 쿼드트리를 구성한 후에 quad() 함수를 이용하여 쿼드 트리를 뒤집는 알고리즘을 사용하였습니다.

    코드는 아래와 같습니다.
    기본 테스트 케이스 및 추가 테스트케이스는 통과하지만
    기타 예측 하지 못한 케이스에서 놓치는 부분이 있거나 코드상에서 빠트리는 부분이 있을것으로 보여 관련하여 도움 부탁드립니다.

    #include <iostream>
    
    using namespace std;
    
    #define MAX_LENGTH 2000
    
    typedef struct node{
        char data;
        struct node* a1;
        struct node* a2;
        struct node* a3;
        struct node* a4;
    } Node;
    
    int Case = 0;
    int T;
    
    char text[MAX_LENGTH+1] = {0,};
    Node* a1 = 0;
    Node* a2 = 0;
    Node* a3 = 0;
    Node* a4 = 0;
    
    Node* tree;
    
    void quad(Node* node);
    int find(int index, int label, Node* node);
    
    int main()
    {
        if(freopen("sample.txt", "r", stdin) == NULL) return 0;
    
        scanf("%d", &T);
    
        while(Case<T)
        {
            tree = new Node;
            tree->data = 'x';
            tree->a1 = NULL;
            tree->a2 = NULL;
            tree->a3 = NULL;
            tree->a4 = NULL;
    
            a1 = 0;
            a2 = 0;
            a3 = 0;
            a4 = 0;
            scanf("%s",text);
    
            printf("%c",text[0]);
    
            find(1,0, tree);
    
            quad(a3);
            quad(a4);
            quad(a1);
            quad(a2);
    
            printf("\n");
            Case++;
            free(tree);
        }
        return 0;
    }
    
    int find(int index, int label, Node* node)
    {
        int i;
        for( i=label ; i<label+4; i++)
        {
            Node* nd = new Node;
            nd->data = text[index];
            nd->a1 = NULL;
            nd->a2 = NULL;
            nd->a3 = NULL;
            nd->a4 = NULL;
    
            if(text[index]=='x')
            {
                index = find(index+1,(label+10)/10*10, nd);
            }
    
            if((i-label)%4==0){
                node->a1 = nd;
            }else if((i-label)%4==1){
                node->a2 = nd;
            }else if((i-label)%4==2){
                node->a3 = nd;
            }else if((i-label)%4==3){
                node->a4 = nd;
            }
    
            if(i==0) a1 = nd;
            if(i==1) a2 = nd;
            if(i==2) a3 = nd;
            if(i==3) {a4 = nd; }
    
            index++;
        }
        if(i==label+4) index--;
        return index;
    
    }
    
    void quad(Node* node)
    {
        if(node->data=='x')
        {
            printf("x");
            if(node->a3->data=='x'){
                quad(node->a3);
            }else{
                printf("%c",node->a3->data);
                free(node->a3);
            }
            if(node->a4->data=='x'){
                quad(node->a4);
            }else{
                printf("%c",node->a4->data);
                free(node->a4);
            }
            if(node->a1->data=='x'){
                quad(node->a1);
            }else{
                printf("%c",node->a1->data);
                free(node->a1);
            }
            if(node->a2->data=='x'){
                quad(node->a2);
            }else{
                printf("%c",node->a2->data);
                free(node->a2);
            }
        }else{
            printf("%c",node->data);
            free(node);
        }
    }
    

    10년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.