题目描述
筱玛是个快乐的男孩子。
寒假终于到了，筱玛决定请他的朋友们一起来玩迷阵探险。
迷阵可以看做一个n×nn×n的矩阵A，每个格子上有一个有一个数A。
入口在左上角的(1,1)处，出口在右下角的(n,n)处。每一步都只能向下或向右移动一格。最后能获得的经验值为初始经验e与路径上经过的所有数的权值异或和。
求筱玛最大可能获得的经验值。
寒假终于到了，筱玛决定请他的朋友们一起来玩迷阵探险。
迷阵可以看做一个n×nn×n的矩阵A，每个格子上有一个有一个数A。
入口在左上角的(1,1)处，出口在右下角的(n,n)处。每一步都只能向下或向右移动一格。最后能获得的经验值为初始经验e与路径上经过的所有数的权值异或和。
求筱玛最大可能获得的经验值。
输入描述:
第一行两个整数n和e。
接下来n行，每行n个整数，描述矩阵A。
输出描述:
一个整数，表示筱玛最大可能获得的经验值。
示例1
输入
5 2
3 4 7 2 6
3 5 2 9 0
3 8 5 7 3
2 5 3 1 4
9 8 6 3 5
输出
15
链接：https://ac.nowcoder.com/acm/contest/545/D
思路：显然我们直接搜等于是在搜一颗二叉树，复杂度O（2^40）左右，肯定超时。但是我们可以用其他方法搜，先从左上角搜，，搜到对角线，然后把所有答案保存在01字典树里。再从右下角往回搜，遇到对角线直接在字典树搜最大异或，取最大值。
代码：
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = + ;
const int INF = 0x3f3f3f3f;
struct node{
node* Next[];
node(){
for(int i = ; i < ; i++)
Next[i] = NULL;
}
};
node* e[maxn]; //走到对角线（含）
int mp[maxn][maxn];
int n, s;
void add(int x, int pos){
node* a = e[pos];
for(int i = ; i >=; i--){
int v = (x >> i) & ;
if(a ->Next[v] == NULL)
a ->Next[v] = new node();
a = a ->Next[v];
}
}
int query(int x, int pos){
node* a = e[pos];
int ret = ;
for(int i = ; i >= ; i--){
int v = (x >> i) & ;
if(a ->Next[!v] != NULL){
a = a ->Next[!v];
ret += ( << i);
}
else a = a ->Next[v];
}
return ret;
}
void dfs(int x, int y, int sum){
if(x + y == n + ){
add(sum ^ mp[x][y], x);
return;
}
dfs(x + , y, sum ^ mp[x][y]);
dfs(x, y + , sum ^ mp[x][y]);
}
int Max;
void dfsBack(int x, int y, int sum){
if(x + y == n + ){
Max = max(query(sum, x), Max);
return;
}
dfsBack(x - , y, sum ^ mp[x][y]);
dfsBack(x, y - , sum ^ mp[x][y]);
}
int main(){
scanf("%d%d", &n, &s);
for(int i = ; i <= n; i++){
e[i] = new node();
for(int j = ; j <= n; j++){
scanf("%d", &mp[i][j]);
}
}
dfs(, , s);
Max = -;
dfsBack(n, n, );
printf("%d\n", Max);
return ;
}