Найти смещение между двумя матрицами

Question

У меня есть 2 двоичные (rxc) матрицы - Матрица A и Матрица B одинакового размера.Матрица B получается смещением единиц в Матрице A на величину смещения влево / вправо / вверху / внизу.

int a[][] ={
            { 0,0,1,0,0 },
            { 0,1,0,1,0 }, 
            { 1,0,0,0,1 }
        }, 
        b[][] = 
        {
            { 0,0,0,1,0 },
            { 0,0,1,0,1 }, 
            { 0,1,0,0,0 }
        }

В этом случае матрица B смещается на одну строку вправо.Моя цель - найти смещение (например, r + 1) между двумя матрицами.

Мое решение - добавить столбец со всеми 0 в матрицу A и проверить, равен ли он матрице B. Продолжить добавление c-1 столбцы.Повторите тот же процесс для строк.Остановитесь, когда две матрицы равны.

Это кажется очень неэффективным способом сделать это.Есть ли лучший способ сделать это?

Answer 1

В настоящее время ваш алгоритм имеет временную сложность O (RC ^ 2). Я могу предложить решение, которое имеет временную сложность O (rc) с использованием хеширования. Я хотел бы обсудить, как решить проблему для случая, когда матрица смещена вправо на несколько столбцов. Та же идея применима и к другим трем типам смен. Следует отметить, что, как я понимаю, в вашем примере вторая матрица смещена на 1 столбец, а не на 1 строку, поскольку все значения смещены на 1 столбец. Я бы использовал это соглашение в следующем решении.

Предположим, нам даны две матрицы 1xc. Теперь мы можем рассматривать их как двоичные строки с цифрами c. Мы бы хэшировали обе строки и сохраняли значение хеш-функции для всех суффиксов второй строки и всех префиксов первой строки, используя память O (c) и время O (c). Теперь мы можем перебрать все возможные смены и проверить. Например, чтобы проверить, смещена ли матрица на 3 столбца, мы можем просто проверить, равны ли первые три значения второй строки нулю и имеет ли суффикс длины (с-3) второй строки то же значение хеша, что и (c-3) префикс длины первой строки в O (1). Нам нужно было бы сохранить длину самого длинного нулевого префикса второй строки, чтобы сделать это эффективно до начала итерации.

Теперь, когда у нас есть матрица rxc, мы можем хешировать каждый столбец обеих матриц, а затем преобразовать матрицу rxc в строку 1xc, где i-тая цифра строки будет равна значению хеш-функции i -ый столбец матрицы и примените вышеуказанный алгоритм аналогичным образом.