#include "stdio.h"
#include "strings.h"

FILE *inFile;

struct Zeichen {
  char aktZeichen;
  void *z1,*z2,*z3,*z4;
};

int bild[64][512];
int maxN;


int digit2zahl(char wen) {
  if (wen >= 'a') {
    return (wen-'a'+10);
  } else return (wen-'0');
}

int readZahl () {
  char aktChar;
  aktChar = fgetc(inFile);  // 0 überlesen
  aktChar = fgetc(inFile);  // x überlesen
  return digit2zahl(fgetc(inFile)*16+fgetc(inFile));   // Die beiden signifikanten Digits lesen
}

void parseFile() {
  // erst die Zahl lesen
  fscanf(inFile,"#define quadtree_width %i\n",&maxN); 
  fscanf(inFile,"#define quadtree_height %i\n",&maxN); 
  fscanf(inFile,"static char quadtree_bits[] = {\n");
  
  //Zeile für Zeile und Spalte für Spalte einlesen
  int zwN = ((maxN+7)/8);
  for (int j = 0; j < maxN; j++) {
    for (int i = 0; i < zwN; i++) {
      bild[i][j] = readZahl();
    }
    char aktChar;
    aktChar = fgetc(inFile); // '\n' überlesen
  }
}

struct Zeichen *backTrack(int vonX, int vonY, int bisX, int bisY) {
  struct Zeichen *aktPtr;
  aktPtr = new struct Zeichen;

  // Rekursionsende erreicht?
  if ((bisX-vonX) == 0) {
    if (bild[vonX / 8][vonY] & (1 << (vonX % 8)) != 0)
      aktPtr->aktZeichen = 'B';
      else aktPtr->aktZeichen = 'W';
    aktPtr->z1 = NULL;
    aktPtr->z2 = NULL;
    aktPtr->z3 = NULL;
    aktPtr->z4 = NULL;  
  } else {
    // rekursiv weiterarbeiten
    int mitteX = vonX+(bisX-vonX)/2;
    int mitteY = vonY+(bisY-vonY)/2;
    aktPtr->z1 = backTrack(vonX,vonY,mitteX,mitteY);
    aktPtr->z2 = backTrack(mitteX+1,vonY,bisX,mitteY);
    aktPtr->z3 = backTrack(vonX,mitteY+1,mitteX,bisY);
    aktPtr->z4 = backTrack(mitteX+1,mitteY+1,bisX,bisY);
    
    // Zwei Fälle: alle 4 Zeichen sind gleich oder auch nicht
    char z1 = ((struct Zeichen*)aktPtr->z1)->aktZeichen;
    char z2 = ((struct Zeichen*)aktPtr->z2)->aktZeichen;
    char z3 = ((struct Zeichen*)aktPtr->z3)->aktZeichen;
    char z4 = ((struct Zeichen*)aktPtr->z4)->aktZeichen;
    if ((z1 == z2) && (z3 == z4) && (z1 == z4) && (z1 != 'Q')) {
      // Zusammenfassen 
      aktPtr->aktZeichen = z1;
      aktPtr->z1 = NULL;
      aktPtr->z2 = NULL;
      aktPtr->z3 = NULL;
      aktPtr->z4 = NULL;
    } else {
      // einzeln nach oben durchreichen
      aktPtr->aktZeichen = 'Q';
    } 
  } 
  return aktPtr;
}

void writeErg(struct Zeichen *in) {
  if (in == NULL) return;
  printf("%c",in->aktZeichen);
  writeErg((struct Zeichen*)in->z1);
  writeErg((struct Zeichen*)in->z2);
  writeErg((struct Zeichen*)in->z3);
  writeErg((struct Zeichen*)in->z4);
}

int main (){
  // Variablen vorbereiten
  inFile = fopen("quadtree2.in","r");
  parseFile();
  printf("%i\n",maxN);
  writeErg(backTrack(0,0,maxN-1,maxN-1));
  printf("\n");
  
  fclose(inFile);
  return(0);
}