Tree Simple Data Manipulation

Asked by At

We've been tasked to create an Octree that has blue and white voxels. However, I've only been able to get the correct answers for Inputs with Level 1 and Level 2.

Details:

  1. p - denotes that the large voxel still needs to be divided into octants

    • b - voxel is blue
    • w - voxel is white
  2. Assume that voxels that were not assigned any color are white

  3. Input: N denotes how many pairs are to be added to each other

Correct Output:

4096
3072
2048
1184

Input:

4
b
w
pbbbbwwww
pbwbwbwbw
pbpbbwwwwbbwwwwpbbwwwwbbb
ppbbwwwwbbbwwwwbpbbwwwwbb
pppbwwwwwbwwwwwwbwwwwwwbw
pwpwpwbwwwwwbwwwwwbwwwwwb

Octree:

#include <iostream>
#include <queue> 
#include <string>
#include <cmath>
using namespace std; 

int N,lvl;
string s1,s2;
int index_a = 0;
int index_b = 0;
int VCount();

struct Node 
{ 
    char data;
    vector<Node *>child; 
}; 

Node *newNode(char data) 
{ 
    Node *temp = new Node; 
    temp->data = data;
    return temp; 
} 

Node *root;
int Voxels(vector<Node *> _root, int level);


int main() 
{ 
    cin>>N;
    for(int i=0;i<N;i++){
        root = newNode('w');
        cin>>s1;
        cin>>s2;
            lvl = 1;
            for(int j = 0; s1[j] != '\0'; j++){
                if(s1[j] == 'p')
                    lvl++;
            }
        cout<<VCount();
        cout<<'\n';
        index_a = 0;
        index_b = 0;
        lvl = 0;
    }     
return 0;   
}  

int VCount(){

    int _vox = 0;

        for(int l = 0; l < 8; l++)                                                                      //  Level 1
            (root->child).push_back(newNode('w'));   
                if (lvl == 1)
                return Voxels(root->child,1);

            if (lvl >= 2){
                 for(int k = 0; k < 8; k++){                                                             //  Level 2
                    for(int j = 0; j < 8; j++){
                        (root->child[k]->child).push_back(newNode('w'));
                    }
                 }
                _vox = Voxels(root->child,2);


            if (lvl >= 3){
                for(int l = 0; l < 8; ++l){
                    for(int k = 0; k < 8; k++){                                                         //  Level 3
                        for(int j = 0; j < 8; j++){
                            (root->child[l]->child[k]->child).push_back(newNode('w')); 
                        }

                    }
                    _vox += Voxels(root->child[l]->child,3);
                }


                if (lvl == 4){
                    for(int l = 0; l < 8; l++){      
                        for(int k = 0; k < 8; k++){                                                     //  Level 4
                            for(int j = 0; j < 8; j++){
                                for(int i = 0; i < 8; i++)
                                    (root->child[l]->child[k]->child[j]->child).push_back(newNode('w'));   
                            }
                        _vox += Voxels(root->child[l]->child[k]->child,4);
                    }
                  }
                }

            }

        }

    return _vox;  
}

int Voxels(vector<Node *> _root, int level){
int _voxels = 0;
int _ind;
int branch = 0;

        if(s1.size() == 1){
                if(s1[index_a] =='b' || s2[index_b] == 'b')
                    return 4096;
                else
                    return 0;
            }

        index_a++;
        index_b++;
        _ind = index_a;


            if(s1[index_a] != 'p' && s2[index_b] != 'p'){
                for(int i = index_a, j = 0; i < s1.size() && s1[i] != 'p'; i++,j++){
                    if(s1[i] == 'b'){
                        _root[branch]->child[j]->data = 'b';
                        _voxels++;
                    }
                    if(j==7){
                        branch++;
                        j=0;
                    }
                    index_a = i;  
                }
                for(int i = index_b, j = 0; i < s2.size() && s2[i] != 'p'; i++, j++){
                    if(s2[i] == 'b' && s1[_ind] != 'b'){
                        _root[branch]->child[j]->data = 'b';
                        _voxels++;
                    }
                    if(j==7){
                        branch++;
                        j=0;
                    }
                   _ind++;
                }
            }

return (4096/pow(8,level-1))*_voxels;
}

0 Answers