2020-04-01 11:33:32
问题描述：
给定一个n×m矩阵arr，矩阵中的路径定义为从(0, 0) 走到 (n-1, m-1) 且只能往下和往右走。对于每一条路径都有一个goal，goal等于这条路径上经过的所有数的异或。 现在你需要找到有多少条路径上的goal等于target，返回这个数目。
样例
例1:
输入:arr=[[2,1,5],[7,10,0],[12,6,4]],target=11 输出:3 解释: 2 1 5 7 10 0 12 6 4 (0,0)→(1,0)→(2,0)→(2,1)→(2,2). 2^7^12^6^4=11 (0,0)→(1,0)→(1,1)→(1,2)→(2,2). 2^7^10^0^4=11 (0,0)→(0,1)→(1,1)→(2,1)→(2,2). 2^1^10^6^4=11
例2:
输入:arr=[[1,3,3,3],[0,3,3,2],[3,0,1,1]],target=2 输出:5
注意事项
1<=n,m<=20
问题求解：
最简单的思路就是去直接dfs搜索答案，但是如果这样做的话时间复杂度大致是O(2 ^ 40)这个是不能接受的。
本题是一个双向dfs的模版题，可以很简单的通过双向的dfs来降低复杂度到O(2 ^ 20)，这样就可以在时限内完成求解。
时间复杂度：O(2 ^ 20)
Map<Integer, Integer>[][] map;
int m, n, mid, goal;
long res;
public long xorSum(int[][] arr, int target) {
// Write your code here.
m = arr.length;
n = arr[0].length;
mid = n - 1;
goal = target;
map = new Map[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = new HashMap<>();
}
}
if (m == 1 && n == 1) {
if (arr[0][0] == target) return 1;
else return 0;
}
else {
res = 0;
dfs1(arr, 0, 0, 0);
dfs2(arr, m - 1, n -1 , 0);
return res;
}
}
private void dfs1(int[][] arr, int i, int j, int curr) {
if (i >= m || j >= n) return;
curr ^= arr[i][j];
if (i + j == mid) {
if(!map[i][j].containsKey(curr)) map[i][j].put(curr, 0);
map[i][j].put(curr, map[i][j].get(curr) + 1);
return;
}
dfs1(arr, i + 1, j, curr);
dfs1(arr, i, j + 1, curr);
}
private void dfs2(int[][] arr, int i, int j, int curr) {
if (i < 0 || j < 0) return;
if (i + j == mid) {
res += map[i][j].getOrDefault(goal ^ curr, 0);
return;
}
curr ^= arr[i][j];
dfs2(arr, i - 1, j, curr);
dfs2(arr, i, j - 1, curr);
}
图-双向dfs-meet_in_the_middle-1516. 异或和
原文：https://www.cnblogs.com/hyserendipity/p/12611424.html