#include <iostream>
#include <cstdio>
#include <cmath>
#include <thread>
using namespace std;

int bitmap[1010][1010];
int cont=0;
void* findBit(void *tasks){ //função de thread recursiva
    int *instructions=(int *)tasks;
    int inil=instructions[0],inic=instructions[1],l=instructions[2],c=instructions[3];
    int i, j, zero=0, one=0;
    for(i=inil;i<=l;i++){ // confiro se é tudo 1, 0, misturado, ou vazio
        for(j=inic;j<=c;j++){
            if(bitmap[i][j]==1) one++;
            else zero++;
        }
    }
    string *str_ptr = new string;
    if(zero && one){ //se for 0 e 1 crio outras 4 threads que vão analiza os novos 4 quadrantes
        *str_ptr = "D";// antes de tudo salvo na string resposta o "D"
        int lm = (inil+l)>>1; //vejo os limites de linhas e colunas pra recursão
        int cm = (inic+c)>>1;
        pthread_t threads[4];
        int inst[]={inil, inic, lm, cm}; // declaro os argumentos das 4 novas threads
        int inst2[]={inil, cm+1, lm, c};
        int inst3[]={lm+1, inic, l, cm};
        int inst4[]={lm+1, cm+1, l, c};
        pthread_create(&threads[0],NULL,findBit, (void *)inst); //crio as 4 threads
        pthread_create(&threads[1],NULL,findBit, (void *)inst2);
        pthread_create(&threads[2],NULL,findBit, (void *)inst3);
        pthread_create(&threads[3],NULL,findBit, (void *)inst4);
        string *str_ptr_aux; //crio um ponteiro de string auxiliar para receber o retorno das 4 threads que criei
        for(int k=0;k<4;k++){
            pthread_join(threads[k], (void**)&str_ptr_aux); // espero com join as 4 threads e salvo o retorno delas em str_prt_aux
            *str_ptr += *str_ptr_aux; //concateno o valor que o join retornou na string resposta
        }
        pthread_exit(str_ptr); //retorno a string resposta, seja para o main ou para outra thread que a tenha chamado
    }else if(one){ // se for tudo um retorno "1" como string resposta para o main ou para outra a thread que a tenha chamado
        *str_ptr = "1";
        pthread_exit(str_ptr);
    }else if(zero){ // se for tudo um retorno "0" como string resposta para o main ou para outra a thread que a tenha chamado
        *str_ptr = "0";
        pthread_exit(str_ptr);
    }else{ // se for vazia retorno uma string vazia como resposta para a main ou a thread que a tenha chamado
        *str_ptr = "";
        pthread_exit(str_ptr);
    }
}

int main(){
    pthread_t thread;
    int l, c, i, j;
    char s[101010];
    printf("Diga o numero de linhas e colunas -> ");
    scanf("%d %d", &l, &c);
    printf("Digite o Bit Map:\n");
    for(i=0;i<l;i++){ //leio o meu bitmap
        scanf("%s", s);
        for(j=0;j<c;j++){
            int conv=s[j]-'0';
            bitmap[i+1][j+1]=conv;
        }
    }
    int tasks[] = {1,1,l,c}; //escolho os valores do argumento
    pthread_create(&thread,NULL,findBit, (void *)tasks); //crio a thread
    string *str_ptr; // ponteiro de string que vai receber a resposta
    pthread_join(thread, (void**)&str_ptr); //espero ela acabar
    printf("A resposta eh -> ");
    cout << *str_ptr << endl; // printo a resposta
    pthread_exit(NULL);
}