Skip to Content
CTRL K

Xor Paths

Análisis oficial (C++) 

Explicación alternativa

Este problema es bastante similar al problema foco del módulo de meet-in-the-middle. Como indica el editorial oficial, podemos recorrer la grilla en exactamente n+m−2n + m - 2 movimientos. Así, podemos partir los movimientos en dos. Si tenemos xx como la XOR-suma de un lado, entonces sumamos cuántas instancias de k⊕xk ⊕x hay del otro lado. Un lado parte de (1,1)(1, 1) y avanza hacia abajo, y el otro lado parte de (n,m)(n, m) y avanza hacia arriba. Cada lado tendrá la mitad de los movimientos.

Implementación

La solución oficial usa DFS, pero no hace falta. Podemos simplemente iterar sobre subconjuntos. Nótese que al final, cuando contamos el número total de formas, tenemos 11 menos que el número total de movimientos. Esto es porque se necesita un movimiento extra para que los dos lados se encuentren.

Complejidad temporal: O(2n+m−22⋅n+m−22)O(2^{\frac{n + m - 2}{2}} \cdot \frac{n + m - 2}{2})

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
	int n, m;
	ll k;
	cin >> n >> m >> k;
	vector<vector<ll>> grid(n, vector<ll>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { cin >> grid[i][j]; }
	}
	int moves = n + m - 2;
 
	// edge case: 1 x 1 grid so moves = 0
	if (moves == 0) {
		cout << (grid[0][0] == k) << endl;
		return 0;
	}
 
	// loop over all combinations of moves from (0, 0)
	/*
	 * left[i][j][k] = number of ways we can have
	 * an xorsum of k ending at (row, col)
	 */
	vector<vector<map<ll, ll>>> left(n, vector<map<ll, ll>>(m));
 
	int leftmoves = moves / 2;
	for (int i = 0; i < (1 << leftmoves); i++) {
		int r = 0;
		int c = 0;
		ll xorsum = grid[0][0];
		bool in_grid = true;
		for (int j = 0; j < leftmoves; j++) {
			/*
			 * if the j'th bit is a 1, then we increase row number,
			 * otherwise we increase col
			 */
			if (i & (1 << j)) {
				r++;
			} else {
				c++;
			}
 
			if (r >= n || c >= m) {
				// this subset leads to out of the grid
				in_grid = false;
				break;
			}
			xorsum ^= grid[r][c];
		}
		if (in_grid) { left[r][c][xorsum]++; }
	}
 
	ll answer = 0;
 
	// here we do the same thing, but we are going up from (n - 1, m - 1)
	int rightmoves = moves - leftmoves - 1;  // note the minus 1
	for (int i = 0; i < (1 << rightmoves); i++) {
		int r = n - 1;
		int c = m - 1;
		ll xorsum = grid[n - 1][m - 1];
		bool in_grid = true;
		for (int j = 0; j < rightmoves; j++) {
			/*
			 * if the j'th bit is a 1, then we decrease row number,
			 * otherwise we decrease col
			 */
			if (i & (1 << j)) {
				r--;
			} else {
				c--;
			}
 
			if (r < 0 || c < 0) {
				// out of the grid
				in_grid = false;
				break;
			}
			xorsum ^= grid[r][c];
		}
		if (in_grid) {
			// number of ways we merge the two sides so total xor is k
			ll search = k ^ xorsum;
			if (r > 0) {
				// merge with the top spot
				answer += left[r - 1][c][search];
			}
			if (c > 0) {
				// merge with the left spot
				answer += left[r][c - 1][search];
			}
		}
	}
 
	cout << answer << endl;
}
Fundamentos