1567. XOR Path Meet
A delivery drone crosses a warehouse floor described by grid. Each cell holds a nonnegative integer tag. The drone starts at the top-left cell, finishes at the bottom-right cell, and may only step one cell right or one cell down. The signature of a route is the bitwise XOR of the tags of every cell it visits, including the first and the last.
Count the distinct routes whose signature equals k, and return the count as a long. Routes are distinct when they differ in at least one visited cell. A grid with a single cell has exactly one route.
Routes can number in the billions, so listing them is out. The intended solution meets in the middle: count partial routes (keyed by XOR value) from the start to the middle anti-diagonal, do the same backwards from the finish, and match the halves cell by cell. Roughly O(2^((rows + cols) / 2)) time and space.
Example 1
- Input:
- grid = [[5]], k = 5
- Output:
- 1
- Explanation:
A one-cell grid has a single route and its signature 5 equals k.
Example 2
- Input:
- grid = [[1,2],[3,0]], k = 2
- Output:
- 1
- Explanation:
Routes 1,2,0 (XOR 3) and 1,3,0 (XOR 2): exactly one matches k = 2.
Example 3
- Input:
- grid = [[2,1,1],[1,1,0],[1,3,1]], k = 1
- Output:
- 0
- Explanation:
Of the six routes through this 3 by 3 grid, 0 have XOR equal to 1.
Constraints
1 ≤ rows, cols ≤ 18; 0 ≤ grid[r][c], k < 230
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(2^((rows + cols) / 2))
- Space
- O(2^((rows + cols) / 2))