Как получить самую длинную строку из 1 в массиве/матрице

Question

Моя задача - найти «длинную строку» из 1 в массиве. Горизонтальная и вертикальная. массив изготавливается только из 0 и 1, и выглядит, например, так:

4 4 
0 1 1 1 
0 1 0 1 
0 1 1 0 
1 0 1 0 

Вывод должен напечатать [я] [J] из «начиная с» 1, и [я] [J] из «окончание» 1. Итак, горизонтальный должен быть [1] [0] [3] [0].

Я использую функцию getcolor(), чтобы получить значение на [i] [j] месте.

Я думаю об этом для WAAAAY долго, потратил почти целую неделю на это. У меня были некоторые идеи, но никто не работал. Может быть, потому что я новичок в C и совершенно новый для массивов.

Я знаю, что мне нужно пройти через массив, на каждом найденном ему нужно сохранить координаты для «запуска» и перейти к следующему, сохраняя каждый 1 найденный до «конца». После того, как 0 найдено, сравните длину, и если длина наибольшая, перепишите длину. Но мне не удалось написать код правильно. Может ли кто-нибудь помочь мне написать код? Большое спасибо.

Edit: Это то, что у меня есть, но я только в самом начале, и он не работает уже:

if(arr != NULL) { 
    while (j < arr->cols) { 
    while (i <=arr->rows) { 
      if (getcolor(arr, i, j) == 1) { 
       startI = i; 
       startJ = j; 
       break; 
      } 
      else 
      i++; 
    } 
    i=0; 
    while (i <=arr->rows) { 
      if (getcolor(arr, i, j) == 1) { 
       endI = i; 
       endJ = j; 
      } 
      i++; 
    } 
    i=0; 

    printf("start %d %d\nend %d %d\nline %d\n\n", startI, startJ, endI, endJ, line); 
    j++; 
    } 
} 

Answer 1

Извините за слишком поздно. Я не писал это точно, как вы этого хотите, но это действительно поможет вам. Просто прочитайте его, и вы получите эту идею.

Ссылка на код http://pastebin.com/vLATASab

Или просмотреть его здесь:

#include <stdio.h> 

main() 
{ 
    int arr[4][4]; 
    arr[0][0] = 0;arr[0][1] = 1;arr[0][2] = 1;arr[0][3] = 1; 
    arr[1][0] = 0;arr[1][1] = 1;arr[1][2] = 0;arr[1][3] = 1; 
    arr[2][0] = 0;arr[2][1] = 1;arr[2][2] = 1;arr[2][3] = 0; 
    arr[3][0] = 1;arr[3][1] = 0;arr[3][2] = 1;arr[3][3] = 1; 

    int i, j, k; 
    int line, line_start, line_end, line_max = 0; 
    int col, col_start, col_end, col_max = 0; 

    // Horizently 
    for (k=0; k<4; k++) 
    { 
     for (i=0; i<4; i++) 
     { 
      if (!arr[k][i]) continue; 
      for (j=i; j<4; j++) 
      { 
       if (!arr[k][j]) break; 
      } 
      j--; 
      if (j-i+1>line_max) 
      { 
       line = k; 
       line_start = i; 
       line_end = j; 
       line_max = line_end-line_start+1; 
      } 
     } 
    } 

    printf("horizontaly\n"); 
    printf("start: [%d][%d]\n", line, line_start); 
    printf("end: [%d][%d]\n", line, line_end); 

    // Verticaly 
    for (k=0; k<4; k++) 
    { 
     for (i=0; i<4; i++) 
     { 
      if (!arr[i][k]) continue; 
      for (j=i; j<4; j++) 
      { 
       if (!arr[j][k]) break; 
      } 
      j--; 
      if (j-i+1>col_max) 
      { 
       col = k; 
       col_start = i; 
       col_end = j; 
       col_max = col_end-col_start+1; 
      } 
     } 
    } 

    printf("\nverticaly\n"); 
    printf("start: [%d][%d]\n", col_start, col); 
    printf("end: [%d][%d]\n", col_end, col); 

} 

Answer 2

Когда вы застряли на проблему, как это, это помогает разбить его на более мелкие проблемы, которые легче решить. Ваша проблема - прекрасный пример. Похоже, вы пытаетесь решить всю проблему сразу, и, как вы видели, она становится немного волосатой с вложенными петлями и всеми остальными. Итак, как вы можете сделать проблему проще? Ну, было бы проще, если бы вы могли просто щелкнуть пальцами и найти самую длинную линию на одном ряду. Аналогично, было бы неплохо иметь простой способ получить самую длинную строку в одном столбце. Итак, рассмотрим написание функции, подобные этим:

int longestLineInRow(int board[][], int width, int height, int &start, int &end) 
{ 
    // returns length, with start and end being the indices of the beginning and end of the line 
} 

int longestLineInColumn(int board[][], int width, int height, int &start, int &end) 
{ 
    // returns length, with start and end being the indices of the beginning and end of the line 
} 

Теперь легко найти строку с самой длинной строки: вы просто найти самую длинную строку в каждой строке и выбрать строку, которая возвращает наибольшее значение. То же самое для столбцов.

Я не решил проблему поиска самой длинной строки внутри строки или столбца для вас, но это более простая задача, которую вы, вероятно, сможете решить самостоятельно, как только перестанете пытаться решить всю проблему сразу.

Answer 3

Я предполагаю, что функция, которую вы показываете, выполняет только половину проблемы, которая находит самую длинную вертикальную последовательность из 1 секунды. Вам нужно будет написать зеркальную функцию, чтобы найти самую длинную горизонтальную последовательность.

Я расскажу вам ошибки, которые я вижу в своем подходе:

• Вы не вычислять где-нибудь длину найденной последовательности
• Вы не храните длину и индексы самой длинной последовательности
• while (i <=arr->rows) должен быть while (i < arr->rows), иначе вы будете выглядеть также в строке с номером 4, когда вы только грести 0, 1, 2 и 3.
• вы сбрасываете i после обнаружив начало последовательности 1s. i вместо этого следует держать опережения
• Вы экономите также j в startJ, но j не изменится, пока вы изучаете один и тот же столбец
• Вы смотрите только одну последовательность из 1s в колонку
• «по горизонтали» и "по вертикали" должно быть написано с двумя "л" :-)

Answer 4

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

typedef struct field { 
    int rows; 
    int cols; 
    int *field; 
} Field; 

Field init_Field(){//Mock 
    Field f; 
    int data[4][4] = { 
     {0, 1, 1, 1}, 
     {0, 1, 0, 1}, 
     {0, 1, 1, 0}, 
     {1, 0, 1, 0} 
    }; 
    f.rows = 4; 
    f.cols = 4; 
    int size = f.rows * f.cols; 
    f.field = malloc(size * sizeof(*(f.field))); 
    memcpy(f.field, data, size*sizeof(*(f.field))); 
    return f; 
} 

int getcolor(Field *f, int r, int c){ 
    if(r < 0 || r >= f->rows) return -1; 
    if(c < 0 || c >= f->cols) return -1; 
    return f->field[ r * f->cols + c]; 
} 

int search(Field *f, int r, int c, int dr, int dc, int level, int maxLen, int nowMax){ 
    //dr,dc : incremental 
    if(dr > 0 && f->rows - r + level <= nowMax) return -1;//stop search 
    if(dc > 0 && f->cols - c + level <= nowMax) return -1;//stop search 
    if(level == maxLen) 
     return level; 
    if(getcolor(f, r, c)==1) 
     return search(f, r + dr, c + dc, dr, dc, level + 1, maxLen, nowMax); 

    return level; 
} 

int main(){ 
    Field f = init_Field(); 
    int HMaxLen = 0, HMaxRow, HMaxCol; 
    int RMaxLen = 0, RMaxRow, RMaxCol; 
    int r, c, len; 
    for(r = 0; r < f.rows;++r){ 
     for(c = 0; c < f.cols;++c){ 
      len = search(&f, r, c, 0, 1, 0, f.cols, HMaxLen); 
      if(len > HMaxLen){ 
       HMaxLen = len; 
       HMaxRow = r; 
       HMaxCol = c; 
      } 
      len = search(&f, r, c, 1, 0, 0, f.rows, RMaxLen); 
      if(len > RMaxLen){ 
       RMaxLen = len; 
       RMaxRow = r; 
       RMaxCol = c; 
      } 
     } 
    } 
    free(f.field); 
    printf("start %d %d\n end %d %d\n\n", HMaxRow, HMaxCol, HMaxRow, HMaxCol + HMaxLen-1); 
    printf("start %d %d\n end %d %d\n\n", RMaxRow, RMaxCol, RMaxRow + RMaxLen-1, RMaxRow); 
    return 0; 
} 

Answer 5

вы можете попробовать следующее

void Reset(int s[2], int e[2], int cs[2], int ce[2], int *resetState, int cc, int pc) 
{ 
*resetState=0; 
      if(cc>pc) 
      { 
       s[0]=cs[0]; 
       s[1]=cs[1]; 
       e[0]=ce[0]; 
       e[1]=ce[1]; 
      } 
} 
void Decide(int value, int s[2], int e[2], int cs[2], int ce[2], int *resetState, int *cc, int *pc, int i, int j) 
{ 
if(value==0&&*resetState) 
{ 
     Reset(s, e, cs, ce, resetState, *cc, *pc); 
} 
else if(value) 
{ 
      if(*resetState==0) 
      { 
       cs[0]=i; 
       cs[1]=j; 
       if(*cc>*pc) 
       { 
        *pc=*cc; 
       } 
       *cc=0; 
       *resetState=1; 
      } 
      ce[0]=i; 
      ce[1]=j; 
      ++*cc; 
} 
} 

void FindLargestRowNdColumn(int a[20][20],int row, int col, int hs[2], int he[2], int vs[2], int ve[2]) 
{ 
int i, j, rcc=0, rpc=0, ccc=0, cpc=0; 
int chs[2]={0,0}, che[2]={0,0}, cvs[2]={0,0}, cve[2]={0, 0}; 
int resetRow=0, restCol=0; 
for(i=0; i<row; ++i) 
{ 
    for(j=0; j<col; ++j) 
    { 
     Decide(a[i][j], hs, he, chs, che, &resetRow, &rcc, &rpc, i, j); 
     Decide(a[j][i], vs, ve, cvs, cve, &restCol, &ccc, &cpc, i, j); 
    } 
    Reset(hs, he, chs, che, &resetRow, rcc, rpc); 
    Reset(vs, ve, cvs, cve, &restCol, ccc, cpc);  
} 
} 

void main() 
{ 
int a[20][20], indexRow, colIndex; 
int colum, row,hs[2], he[2], vs[2], ve[2]; 
printf("Enter number of rows and columns\n"); 
scanf("%d%d", &row, &colum); 
printf("Enter the array\n"); 
for(indexRow=0; indexRow<row; ++indexRow) 
{ 
    for(colIndex=0; colIndex<colum; ++colIndex) 
    { 
     scanf("%d", &a[indexRow][colIndex]); 
    } 
} 
FindLargestRowNdColumn(a, row, colum, hs, he, vs, ve); 
printf("Row [%d][%d] [%d][%d]\n", hs[0], hs[1], he[0], he[1]); 
printf("column [%d][%d] [%d][%d]\n", vs[0], vs[1], ve[0], ve[1]); 
}