- 异或路径(xorpath)
救救OJ,关闭孩子吧!
- @ 2026-4-4 23:15:23
#include <bits/stdc++.h>
using namespace std;
const int maxn = 25;
typedef unsigned long long ULL;
int n, m, ans;
ULL k, a[maxn][maxn];
unordered_map<ULL, int> res[maxn][maxn];
int total_step, half_step;
void dfs1(int x, int y, ULL now, int step);
void dfs2(int x, int y, ULL now, int step);
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> k;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
cin >> a[i][j];
}
}
total_step = n + m - 2, half_step = total_step / 2;
dfs1(1, 1, a[1][1], 0);
dfs2(n, m, a[n][m], 0);
cout << ans;
return 0;
}
void dfs1(int x, int y, ULL now, int step) {
if (step == half_step) {
res[x][y][now]++;
return;
}
if (x + 1 <= n) dfs1(x + 1, y, now ^ a[x + 1][y], step + 1);
if (y + 1 <= m) dfs1(x, y + 1, now ^ a[x][y + 1], step + 1);
}
void dfs2(int x, int y, ULL now, int step) {
if (step == total_step - half_step) {
ans += res[x][y][k ^ now ^ a[x][y]]; // X ^ Y = Z
return;
}
if (x - 1 >= 1) dfs2(x - 1, y, now ^ a[x - 1][y], step + 1);
if (y - 1 >= 1) dfs2(x, y - 1, now ^ a[x][y - 1], step + 1);
}
求调
1 条评论
-
yujichen LV 3 @ 2026-4-26 13:01:23
把 ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); 删了试试
- 1
信息
- ID
- 582
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 56
- 已通过
- 6
- 上传者