首先你一路爆搜过去结果肯定是对的。
但是你从左上角走到右下角需要 \(2(n-1)\) 步，而每一步有两种选择，则总共有 \(2^{2(n-1)}\) 种路径搜不死你。
如何优化呢？我们连接右上角和左下角，钦定这一条对角线上的点是“转折点”。
当我们的搜搜搜程序到达某个转折点时，就可以了！
再钦定一个计数器 \(f[x][y][val]\)，表示从左上角到转折点 \((x,y)\) 时路径异或值为 \(val\) 的方案数。
由于异或有性质：\(a\oplus a=0\)（\(\oplus\) 表示异或，即 ^ 运算符）
那么只要我们再从右下角搜搜搜到转折点，然后看能结出几条路就可以了。
#include <map>
#include <stdio.h>
int val[25][25];
int n,i,j;
long long res;
std::map<long long,int> f[25][25];//注意long long。
const int dx[5]={0,1,0,-1,0};
const int dy[5]={0,0,1,0,-1};
inline void fill(int x,int y,int dep)//从左上角搜！搜！搜！
{
dep^=val[x][y];//注意这两段程序中这句话的位置是不同的。
if(x+y==n+1)
{
++f[x][y][dep];
return ;
}
fill(x+dx[1],y+dy[1],dep);
fill(x+dx[2],y+dy[2],dep);
return ;
}
inline void solve(int x,int y,int dep)//从右下角搜！搜！搜！
{
if(x+y==n+1)//对角线性质：行列数相加为n+1.
{
res+=f[x][y][dep];//现在路上是dep，dep^dep=0
return ;
}
dep^=val[x][y];
solve(x+dx[3],y+dy[3],dep);
solve(x+dx[4],y+dy[4],dep);
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
scanf("%d",val[i]+j);
fill(1,1,0);
solve(n,n,0);
printf("%lld",res);
return 0;
}