XOR путь
XOR путь
Дана матрица a размера n * n из целых чисел.
Предположим, что строки матрицы пронумерованы сверху вниз от 1 к n, а столбцы слева направо от 1 к n. Пусть ai,j
- число на пересечении i - ой строки и j - го столбца.
Вы начинаете путь в клетке (1, 1) и можете двигаться только вниз и вправо. Путь нужно закончить в клетке (n, n). Пусть b1
, b2
, . . ., b2n−1
- целые числа, записанные в клетках, которые Вы посетили.
Цена пути равна b1
⊕ b2
⊕ . . . ⊕ b2n−1
.
Найдите путь от (1, 1) до (n, n) с минимальной ценой.
Входные данные
Первая строка содержит одно целое число n (2 ≤ n ≤ 20) - размер матрицы.
Каждая из следующих n строк содержит n целых чисел ai1
, ai2
, . . . , ain
(1 ≤ aij
≤ 109
).
Выходные данные
Выведите одно целое число - минимально возможную цену пути.
Примечание
Выражение x ⊕ y означает применение побитовой операции XOR к числам x та y. Данная операция существует во всех современных языках программирования, например, в языках С++ и Java она обозначена как «ˆ», а в Pascal как «xor».
2 1 8 2 8
1
4 99 146 613 1416 513 5810 1515 9616 1247 5124 6284 5844 1139 6135 6427 1561
241