Вставка и сдвиговая матрица n * n

Question

У меня есть матрица N * N.

Мне нужно реализовать функцию, которая получает Num 0/1, вставить его в матрицу и проверить, есть ли строка/столбец со всеми 1.

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

0 1 0 
1 1 0 
0 0 0 

И мы вводим 1, так что теперь, чтобы матрица выглядеть следующим образом:

1 0 1 
0 1 1 
0 0 0 

Если теперь мы подставим 0, так что матрица выглядит следующим образом:

0 1 0 
1 0 1 
1 0 0 

У меня есть идея сделать правый сдвиг в матрицу, и я возьму время o (n^2).

Есть еще идеи по реализации функции, которая вставляет значение (0/1) и проверяет наличие строки и столбца со всеми 1?

Спасибо!

Answer 1

Матрица обычно реализуется в виде массива в памяти, причем каждый (x,y) месте индексированного в x*w + y, где w является ширина массива (x и y с нуля). Печать массива так же просто, как вставка новой строки после каждого w элементов.

Это делает вставку O(n). Просто сдвиньте каждый элемент на одну позицию в массиве.