P3532.第3题-回文

1000ms

Difficulty: 7

所属公司 : oppo

算法与标签>位运算

题目内容

给定一个大小为 $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})$ ，表示棋盘上每个格子的初始数字。

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

输入

2
1 1
1 3

输出

说明

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

输入

输出

输入

预期输出（选填）