Поиск самого населенного района в матрице игры жизни

Я запрограммировал игру «Жизнь» на C, и она работает хорошо, единственная проблема — игровое поле намного больше, чем можно отобразить. Я знаю количество строк и столбцов, которые может отображать монитор, и я подумал, что было бы неплохо, так сказать, следить за действием (поиск самой густонаселенной области). Поэтому я написал небольшую функцию для получения 4 индексов углов той части поля, которую я должен отобразить, но каким-то образом код, кажется, дает случайные участки, которые иногда заведомо ложны, рассчитанную стоимость живых ячеек (макс.) совершенно ложно (иногда даже больше, чем вся матрица сама по себе). Вот код:

int* most_populated_area(int m, int n, bool a[m][n], int r, int c){
    int * rr=malloc(sizeof(int)*4); //return value
    rr[0]=0;
    rr[1]=r;
    rr[2]=0;
    rr[3]=c; //we first assume that the most populated arrea is upper left corner
    int summe=0;
    int max=0; //to controll wheater or not we found a more populated area we need a summe and the max we founded until now
    for(int isearch=0; isearch<m; isearch++){ //we search the matrix row for row
        for(int jsearch=0; jsearch<n; jsearch++){ // and column for column
            for(int ik=0; ik<=r; ik++){ // now from the current flied we go as many rows we are allowed
                for(int jl=0; jl<=c; jl++){ //and also as many columns we are allowed to go
                    int iks=isearch+ik; //we looking on the field is 0 to r
                    int jls=jsearch+jl; //and 0 to c flieds away from our current field
                    if(iks>=m){ //if the field is outside the matrix we have to go back  
                        iks%=r; // iks is clearly bigger than r (because m bigger than r) but iks%r can be r-1 at most,
                        //so we have the rest from iks through r over the edge 
                    }
                    if(jls>=n){ //analog to iks
                        jls%=c;
                    }
                    summe+=a[iks][jls];
                }
            }
            if(summe>max){// the summe is greater than the max we found a more populated area and we save the the results
                max=summe;
                rr[0]=isearch;
                rr[1]=(isearch+r>=m)?(isearch+r)%r:isearch+r;
                rr[2]=jsearch;
                rr[3]=(jsearch+c>=n)?(jsearch+c)%c:jsearch+c;
            }
            summe=0; //anyway we reset the summe to search accurate
        }
    }
    printf("Lifing in this area %d \n", max);
    return rr;
}

person user3284214    schedule 08.01.2016    source источник
comment
Слишком много вложенных циклов for, вы уверены, что другого выхода нет?   -  person Iharob Al Asimi    schedule 09.01.2016
comment
Кроме того, самый населенный район какого размера?   -  person Iharob Al Asimi    schedule 09.01.2016
comment
Размер r на c   -  person John Hascall    schedule 09.01.2016
comment
Можно несколько упростить, выполнив: for (int isearch = 0; isearch < (m - r); isearch++) и соответствующее изменение на другой оси. Это может даже решить вашу проблему, поскольку эти: if (iks >= m) { iks %= r; } мне кажутся неправильными.   -  person John Hascall    schedule 09.01.2016
comment
Если вы отображаете прямоугольную область, вы можете просто просмотреть и попробовать каждую возможную область. Таким образом, это займет O((n-n1)*(m-m1)*n1*m1) времени, если ваша доска n x m, а размер прямоугольника n1 x m1. Это может подойти для размера вашей доски/прямоугольника.   -  person Timothy Murphy    schedule 09.01.2016
comment
Мой монитор отображает 1920x1080 пикселей. Вы используете текстовую консоль, скажем, 80x25 символов?   -  person Weather Vane    schedule 09.01.2016
comment
Я бы сказал, что мне нужно 4 цикла, чтобы я тщательно искал, моя идея заключалась в том, чтобы каждый летал в верхнем левом углу поля, чтобы отображать и видеть, сколько заполнено в этом поле.   -  person user3284214    schedule 09.01.2016
comment
@Vane Да, я использую консоль для отображения этого, также окно не всегда заполнено.   -  person user3284214    schedule 09.01.2016
comment
@Murphy, это тоже была моя идея, я получаю каждую область, где каждое поле находится в верхнем левом углу, поэтому я использую свои 4 цикла.   -  person user3284214    schedule 09.01.2016
comment
Я не могу решить вашу проблему, кроме как сказать: сдвиньте гору и стремитесь к презентации с графическим интерфейсом: 1 пиксель на жизнь.   -  person Weather Vane    schedule 09.01.2016
comment
@Hascall Как бы ваш метод нашел больше людей в правой половине матрицы? Да, я также подозреваю, что ошибка где-то здесь, но поле может приостанавливать края матрицы и снова появляться в строке/столбце 0.   -  person user3284214    schedule 09.01.2016


Ответы (1)


Существует приближенное решение, равное O(n).

Разделите доску на компоненты x и y и найдите наиболее заполненные значения X и Y. Затем установите их как средние точки (с поправкой на края), которые будут отображаться.

person cwallach    schedule 08.01.2016