分数: 425 点
问题陈述
有一个网格 H 行和 W 列。 让 (i,j) 表示位于 i从顶部算起的第行 (1\leq i\leq H) 和 j左起第 列 (1\leq j\leq W).
细胞 (i,j)\ (1\leq i\leq H,1\leq j\leq W) 有一个非负整数 A_{i,j} 。
让我们在网格上放置零个或多个多米诺骨牌。 多米诺骨牌覆盖两个相邻的单元格,即以下对之一:
- 细胞 (i,j) 和 (i,j+1) 为 1\leq i\leq H,1\leq j\lt W;
- 细胞 (i,j) 和 (i+1,j) 为 1\leq i\lt H,1\leq j\leq W.
任何单元格都不能被多于一张多米诺骨牌覆盖。
对于多米诺骨牌的放置,定义其 分数 游戏的 作为单元格中写入的所有整数的按位异或 不 被任何多米诺骨牌覆盖。
找到可能的最大分数。
什么是按位异或?
对于非负整数 A 和 B,它们的按位异或 A \oplus B 定义如下:
- 在二进制中, 2^k 位(k \ge 0)的 A \oplus B is 1 如果恰好是以下之一 A 和 B 有 1 在那一点上,并且 0 否则。
对于 k 非负整数 p_1, p_2, p_3, \dots, p_k,它们的按位异或是 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),可以证明与操作数的顺序无关。
约束
- 1 \le H
- 1 \le W
- HW \le 20
- 0 \le A_{i,j} < 2^{60} (1 \le i \le H,\ 1 \le j \le W)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W
A _ {1,1} A _ {1,2} \ldots A _ {1,W}
A _ {2,1} A _ {2,2} \ldots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \ldots A _ {H,W}
输出
输出答案。
示例输入 1
3 4 1 2 3 8 4 0 7 10 5 2 4 2
示例输出 1
15
网格如下:

例如,以下位置的得分为 15.

没有任何展示位置得分达到 16 或更高,因此输出 15.
示例输入 2
1 11 1 2 4 8 16 32 64 128 256 512 1024
示例输出 2
2047
您也可以选择不放置多米诺骨牌。
示例输入 3
4 5 74832 16944 58683 32965 97236 52995 43262 51959 40883 58715 13846 24919 65627 11492 63264 29966 98452 75577 40415 77202
示例输出 3
131067