CSES Book "Pruning the search"

all-paths.cc

#include<bits/stdc++.h>
using namespace std;

#define en cout<<"\n";
#define ll long long

auto clk = clock();

ll n;
ll ans = 0;
bool vis[100][100];
vector<pair<ll,ll>> res;

void backtrack(ll x, ll y, ll n) {
    if(x<0 || y<0 || x>n-1 || y>n-1) return;
    if(vis[x][y]) return;
    vis[x][y] = true;
    // optimization 3
    if(y == 0 && x-1 >= 0 && x+1<=n-1 && !vis[x-1][y] && !vis[x+1][y]) {
        vis[x][y] = false;
        return;
    }
    if(y == n-1 && x-1 >= 0 && x+1<=n-1 && !vis[x-1][y] && !vis[x+1][y]) {
        vis[x][y] = false;
        return;
    }
    if(x ==0 && y-1 >=0 && y+1 <=n-1 && !vis[x][y-1] && !vis[x][y+1]) {
        vis[x][y] = false;
        return;
    }
    if(x ==n-1 && y-1 >=0 && y+1 <=n-1 && !vis[x][y-1] && !vis[x][y+1]) {
        vis[x][y] = false;
        return;
    }
    res.push_back({x,y});
    if(x==n-1 && y==n-1) {
        // optimization 2
        if(res.size()!=n*n) {
            vis[x][y] = false;
            res.pop_back();
            return;
        }
        ++ans;
    }
    // optimization 1
    if(res.size()!=1) {
        backtrack(x,y+1,n);
    }
    backtrack(x-1,y,n);
    backtrack(x+1,y,n);
    backtrack(x,y-1,n);
    vis[x][y] = false;
    res.pop_back();
}

int main() {
    cin>>n;
    memset(vis, false, sizeof(vis));
    backtrack(0,0,n);
    cout<<ans*2;
    

    #ifdef AMAN
        en;en;en;cout<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC;en;
    #endif
}