Определить последовательное повторение в двумерном массиве [C] - PullRequest
Новая
       39

Определить последовательное повторение в двумерном массиве [C]

0 голосов
/ 12 мая 2011

У меня есть двумерный массив, который выглядит следующим образом: 

1 1 0 0 1
1 0 1 1 0
0 0 1 1 0
1 1 0 1 1
0 0 1 1 1

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

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

Пока что у меня есть что-то вроде этого (только для проверки): 

main() {
    ...
    for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
        if (G[i][j] == 1) {
          CheckAcross(i, j, n);
        }
    ...
}

void CheckAcross (int i, int j, int n) {
     if (i < 0 || i >= n || j < 0 || j >= n) return; // outside of grid
     if (G[i][j] == 0 ) return; //0 encountered
     G[i][j] = WordCount + 1;
     CheckAcross(i, j + 1, n);

}

, где G[][] - это двумерный массив, содержащий 1 и 0, n - количество строк / столбцов, i - номер строки и j - номер столбца.

Спасибо за любую помощь заранее!

Ответы [ 2 ]

0 голосов
/ 14 мая 2011

Создайте новую матрицу n-n-n с именем V. Она будет хранить для каждой ячейки число 1 в этой ячейке и непосредственно над ней . Это будет O (n ^ 2). 

checkAllVertical(int n) {
    V = malloc(....) // create V, an n-by-n matrix initialized to zero
    for(int r=0; r<n; r++) {
      for(int c=0; c<n; c++) {
        if(G[r][c]=1) {
          if(r==0)
            V[r][c] = 1;
          else
            V[r][c] = 1 + V[r][c];
        }
      }
    }
}

Вам не нужно выделять все V. Достаточно одной строки за раз.

0 голосов
/ 12 мая 2011

Ваш текущий ответ займет время O (n 3 ); чтобы оценить одну строку, вы проверяете каждую возможную начальную и конечную позиции (O (n) возможностей для каждой), и есть n строк.

Ваш алгоритм верен, но давайте посмотрим, сможем ли мы улучшить время выполнения.

Проблема может упроститься, если разбить ее на более простые задачи, т. Е. «Какова самая длинная непрерывная цепочка из 1 в этом одномерном массиве?». Если мы решим его 2n раз, то у нас есть наш ответ, поэтому нам просто нужно уменьшить его до O (n 2 ) для улучшения.

Ну, мы можем просто пройти через строку, помня позицию (начало и конец) и длину самой длинной последовательности 1 с. Это занимает время O (n) и является оптимальным (если все последовательности равны 1 или 0, нам нужно прочитать каждый элемент, чтобы узнать, где находится начало / конец самой длинной последовательности).

Тогда мы можем просто решить это для каждой строки и каждого столбца за O (n 2 ) времени.

...