логическая матрица, как эффективно найти строку / столбец с истинным значением

Question

Я пытаюсь найти эффективное решение для следующей загадки:

1. У меня есть логическая матрица с размером ( n * n ), заполненным false значения
2. мне нужно создать функцию, которая получит ноль или единицу в качестве аргумента , она сместит все значения в матрице на один шаг влево (имеется в виду первый элемент напервая строка удаляется, и последний элемент в последней строке является нашим новым битом) и возвращает значение true, если в нашей матрице есть строка / столбец, содержащий только свои значения.

Нет ограничений на структуру данных.

Мое наивное решение в javascript:

const next = (bit, matrix) => {
  matrix.shift()
  matrix.push(bit);

  const matrix_size = Math.sqrt(matrix.length);

  let col_sum = 0;
  let row_sum = 0;

  for (let i = 0; i < matrix.length; ++i) {
    col_sum = matrix[i];
    row_sum += matrix[i];

    if ((i + 1) % matrix_size === 0) {
      if (row_sum === matrix_size) return true;

      row_sum = 0;
    }

    for (let j = i + matrix_size;j < (i + ((matrix_size * matrix_size) - 1)); j += matrix_size) {
      col_sum += matrix[j];
    }

    if (col_sum === matrix_size) return true;
  }

  return false;
}

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

Люблю слышать некоторые идеи:)

Answer 1

Давайте подумаем о следующем примере матрицы:

[0, 0, 0, 0,
 0, 0, 0, 0,
 0, 0, 1, 1,
 1, 1, 1, 1]

и нажмите ноль 16 раз.
Затем будут получены значения «Ложь», «Истина», «Истина», «Ложь», «Истина», «Истина», «Истина», «Ложь», «Истина», «Истина», «Ложь», «Ложь» и «Ложь».
Существует циклическое поведение (False, True, True, True).
Если длина продолженных записей была фиксированной, нет необходимости пересчитывать каждый раз при обновлении.
Обновлена ​​матрица, можно изменить длину продолжения в верхнем левом и нижнем правом углу, и это может потребоваться для обновления циклической памяти.
Поддержание продолженных последовательностей, поддержание общего количества циклического поведения, на которое влияют последовательности, сложность для строк будет в O(1).

В случае столбца, вместо смещения и нажатия, пусть matrix[cur]=bit и cur = (cur+1)%(matrix_size*matrix_size) представляют cur как фактический верхний левый угол матрицы.
Поддерживая col_sum каждого столбца, поддерживая общее количество, удовлетворяющее условию «все единицы», сложность будет O(1).

class Matrix:
  def __init__(self, n):
    self.mat = [0] * (n*n)
    self.seq_len = [0] * (n*n)
    self.col_total = [0] * n
    self.col_archive = 0
    self.row_cycle_cnt = [0] * n
    self.cur = 0
    self.continued_one = 0
    self.n = n

  def update(self, bit):
    prev_bit = self.mat[self.cur]
    self.mat[self.cur] = bit

    # update col total
    col = self.cur % self.n
    if self.col_total[col] == self.n:
      self.col_archive -= 1
    self.col_total[col] += bit - prev_bit
    if self.col_total[col] == self.n:
      self.col_archive += 1

    # update row index
    # process shift out
    if prev_bit == 1:
      prev_len = self.seq_len[self.cur]
      if prev_len > 1:
        self.seq_len[(self.cur + 1) % (self.n * self.n)] = prev_len-1
      if self.n <= prev_len and prev_len < self.n*2:
        self.row_cycle_cnt[self.cur % self.n] -= 1
    # process new bit
    if bit == 0:
      self.continued_one = 0
    else:
      self.continued_one = min(self.continued_one + 1, self.n*self.n)
      # write the length of continued_one at the head of sequence
      self.seq_len[self.cur+1 - self.continued_one] = self.continued_one
      if self.n <= self.continued_one and self.continued_one < self.n*2:
        self.row_cycle_cnt[(self.cur+1) % self.n] += 1

    # update cursor
    self.cur = (self.cur + 1) % (self.n * self.n)

    return (self.col_archive > 0) or (self.row_cycle_cnt[self.cur % self.n] > 0)

  def check2(self):
    for y in range(self.n):
      cnt = 0
      for x in range(self.n):
        cnt += self.mat[(self.cur + y*self.n + x) % (self.n*self.n)]
      if cnt == self.n:
        return True
    for x in range(self.n):
      cnt = 0
      for y in range(self.n):
        cnt += self.mat[(self.cur + y*self.n + x) % (self.n*self.n)]
      if cnt == self.n:
        return True
    return False


if __name__ == "__main__":
  import random
  random.seed(123)
  m = Matrix(4)
  for i in range(100000):
    ans1 = m.update(random.randint(0, 1))
    ans2 = m.check2()
    assert(ans1 == ans2)
    print("epoch:{} mat={} ans={}".format(i, m.mat[m.cur:] + m.mat[:m.cur], ans1))