Количество возможных путей данной матрицы, имеющих побитовое исключающее ИЛИ, равное K

Опубликовано: 19 Сентября, 2022

Дана матрица N*M (N + M ≤ 40) mat[][] , каждая ячейка имеет некоторое значение в диапазоне от 0 до 10 18 и целое число K . Найдите количество всех возможных путей, для которых побитовое исключающее ИЛИ элементов пути равно K . Движение разрешено только вправо и вниз.

Примеры:

Input: N = 3, M = 4, K= 2
mat[][] = { {1, 3, 3, 3},
                 {0, 3, 3, 2},
                 {3, 0, 1, 1} }
Output: 5
Explanation: All possible paths are: 
(1,1)→(2,1)→(2,2)→(3,2)→(3,3)→(3,4) =  1^0 ^3^0^1^1 = 2
(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(3,4) = 1^0^3^0^1^1 = 2
(1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(3,4) = 1^0^3^3^2^1 =2
(1,1)→(1,2)→(1,3)→(2,3)→(3,3)→(3,4) = 1^3^3^3^1^1 =2
(1,1)→(1,2)→(2,2)→(2,3)→(3,3)→(3,4) =  1^3^3^3^1^1 =2

Input: N = 3, M = 3, K =11
 mat[][] = { {2, 1, 5},
                  {7, 10, 0},
                  {12, 6, 4} }
Output: 3
Explanation:All possible paths are: 
(1,1)→(2,1)→(3,1)→(3,2)→(3,3) = 2 ^ 7 ^12 ^ 6 ^4 =11
(1,1)→(2,1)→(2,2)→(2,3)→(3,3) = 2 ^ 7 ^ 10 ^ 0 ^4 =11
(1,1)→(1,2)→(2,2)→(3,2)→(3,3) = 2^1^10^ 6 ^ 4 = 11 

Наивный подход: простой подход состоит в том, чтобы пройти все возможные пути и проверить, равен ли XOR этого пути K или нет. При этом используйте откат, так как в любой данной ячейке будет два варианта: идти вправо или вниз, и это станет двумя рекурсивными операторами в решении с возвратом.

Ниже приведена реализация вышеуказанного подхода:


Сложность времени: O(2 X * X), где X = (N + M – 2)
Вспомогательное пространство: О(1)

Почему просто Backtracking здесь не сработает?
Количество ходов, необходимых для перехода от ( 1, 1) к (N, M) , будет равно (N+M-2) . Теперь, используя решение для рекурсивного поиска с возвратом, потребуется O(2 (N+M-2) ) времени, чтобы перебрать все пути этой длины и проверить, имеет ли каждый путь XOR, равный K , или нет. Для более высоких значений (N+M) этот алгоритм становится очень трудоемким, поскольку значение приближается к приведенному здесь ограничению.

Эффективный подход: использование алгоритма «Встреча посередине» разделяет количество шагов и делает (N + M — 2)/2 в первой половине, остальные шаги — в следующей половине. Выполните шаги, указанные ниже, чтобы решить проблему:

  • И объедините ответы двух решений, что в основном является стандартной идеей алгоритма Meet in the Middle.
  • Разделите эту маску из n+m-2 битов на две части: mid = (n+m-2)/2 бита и (n+m-2)-mid бит.
  • Для левой части:
    • Выполните рекурсивный возврат, начиная с ячейки (1,1) и вниз , и сохраняйте xor пути для средних шагов. после промежуточных шагов у нас есть позиция индекса, т.е. (i,j) и значение xor до этой точки, и мы вычисляем, сколько таких триплетов выходит {zor, i,j}
  • Для правой части:
    • Выполните рекурсивный возврат, начиная с ячейки (N, M) и влево или вверх , и сохраняйте xor пути для
      (N+M-2) – середина -1 шагов.
  • после средних шагов находится позиция индекса, т.е. (i,j), и значение xor до этой точки, и вычисляется, сколько таких триплетов выходит {zor, i,j}
  • После написания кода для обеих частей теперь пройдите триплеты второй части и проверьте, есть ли за один шаг, т.е. (i-1,j) или (j-1, i), тройка, имеющая xor K в триплетах левой части.

Ниже приведена реализация вышеуказанного подхода:


Сложность времени: O(X * 2 X ), где X = (N + M – 2)/2
Вспомогательное пространство: O(N + M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ