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

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

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

Я пытаюсь найти способ определить самую длинную непрерывную цепочку из 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 — номер столбца.

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


recursion multidimensional-array backtracking contiguous
person Zach S    schedule 12.05.2011    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

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

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

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

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

person Community    schedule 12.05.2011
comment
Если вы хотите придерживаться своего собственного решения, вы можете легко поменять местами строки и столбцы, просто поменяв местами индексы, и ваша реализация готова. - person ; 12.05.2011

arrow_upward
0
arrow_downward

Создайте новую матрицу n на n с именем V. В ней для каждой ячейки будет храниться количество единиц в этой ячейке и непосредственно над ней. Это будет 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. Достаточно одной строки за раз.

person Aaron McDaid    schedule 14.05.2011