Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll n, m, k;
- vector<vector<ll>> grid;
- map<ll, ll> freq[20][20];
- void search1(ll x, ll y, ll stop, ll xv){
- if(x>=n || y>=m){
- return;
- }
- xv^=grid[x][y];
- //ll nx = grid[x][y]^xv;
- //xv = nx;
- //cout << "x: " << x << ", y: " << y << ", xv: " << nx << '\n';
- if(stop==0){
- //int val = xor^grid[x][y];
- freq[x][y][xv]++;
- //cout << "STOP" << '\n';
- //cout << "x: " << x << ", y: " << y << ", xv: " << xv << ", freq[x][y][xv]: " << freq[x][y][xv] << '\n';
- return;
- }
- search1(x+1, y, stop-1, xv);
- search1(x, y+1, stop-1, xv);
- }
- ll search2(ll x, ll y, ll stop, ll xv){
- //!!!Answer must also be able to be returned as a long long so
- //search function needs to be declared using long long
- if(x<0 || y<0){
- return 0;
- }
- //cout << "x: " << x << ", y: " << y << '\n';
- if(stop==0){
- //cout << "STOP" << '\n';
- //xv^=grid[x][y];
- ll val = xv^k;
- //cout << "xv: " << xv << ", val: " << val << '\n';
- //cout << "val: " << val << '\n';
- //int ret = 0;
- if(freq[x][y].count(val)>0){
- //cout << ", freq[x][y][val]: " << freq[x][y][val] << '\n';
- return freq[x][y][val];
- }
- return 0;
- }
- xv^=grid[x][y];
- return search2(x-1, y, stop-1, xv)+search2(x, y-1, stop-1, xv);
- }
- int main(){
- //freopen("xorpaths.in", "r", stdin);
- cin >> n >> m >> k;
- grid.resize(n, vector<ll>(m));
- for(ll i=0; i<n; i++){
- for(ll j=0; j<m; j++){
- cin >> grid[i][j];
- }
- }
- ll tot = (n+m)-2;
- ll half = tot/2;
- search1(0, 0, half, 0);
- //cout << "=========" << '\n';
- //!!!Need to use two searches to get values and meet in the
- //of the grid to prevent time limit exceeded
- cout << search2(n-1, m-1, tot-half, 0) << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
