思路与证明

• 关键结构：行回文要求 $(i,j)$ 与 $(i, n-1-j)$ 最终相等；列回文要求 $(i,j)$ 与 $(n-1-i, j)$ 最终相等。两者合并，任意四元组

  $$(i,j),\ (i, n-1-j),\ (n-1-i, j),\ (n-1-i, n-1-j)$$

  在最终结果中应相等。

• 分组：

题目内容

给定一个大小为 $n×n$ 的棋盘，第 $i$ 行第 $j$ 列上的数字为 $a_{i,j}$ 。

将格子 $(i,j)$ 上的数字修改为非负整数 $x$ 的代价为 $a_{i,j}$ $xor$ $x$ 。

请你计算，使得棋盘的每一行和每一列均为回文所需的最小总代价。

【名词解释】 $xor$：表示位运算中的按位异或运算。

回文：从左往右读和从右往左读都相同的字符串。在本题中，记第 $k$ 行的数字序列为 $b_1,b_2,...,b_n$ ，则 $b_1,b_2,...,b_n$ 是回文的当且仅当 $b_i = b_{n-i+1}$ 对任意 $1≦i≦n$ 成立。

输入描述

第一行输入一个整数 $n(1 ≦ n≦ 800)$ ，表示棋盘的大小。

此后 $n$ 行，第 $i$ 行输入 $n$ 个整数 $a_{i,1},a_{i,2},···,a_{i,n}(1≦a_{i,j}< 2^{30})$ ，表示棋盘上每个格子的初始数字。

输出描述

输出一个整数，表示将棋盘调整为每行每列均为回文所需的最小总代价。

样例1

输入

2
1 1
1 3

输出

2

说明

在这个样例中，使得 $a_{2,2}=1$ 即可。

样例2

输入

3
1 2 3
6 5 4
9 7 8

输出

26