Number of solutions there are in an n*n grid for(1,1 to n,n)visiting all squares

PHOTO EMBED

Fri Nov 06 2020 03:45:15 GMT+0000 (UTC)

Saved by @Shami_Al #c++

/**
   SHAMI AL BASHAR PROTHOY
   PRESIDENCY INTERNATIONAL SCHOOL
**/

#include <bits/stdc++.h>
using namespace std;
#define csee "Case "<<cs<<": "
typedef long long ll;
typedef long double ld;
#define B begin()
#define E end()
#define F first
#define S second
#define pb push_back
#define pp pop_back
#define ins insert
#define vi vector
const ld pi=2*acos(0.0);
ll T,N;
ll cs=1;
ll soln=0;
/**
THINK TWICE,
      CODE ONCE
**/
bool ok(vi<vi<ll>>&v,ll row,ll col)
{
    if(row>=0&&row<N&&col>=0&&col<N&&!v[row][col])
        return true;
    return false;
}
void go(vi<vi<ll>>&v,ll row,ll col,ll tp)
{
    if(row==N-1&&col==N-1)
    {
        if(N*N==tp)
            soln++;
        return;
    }
    v[row][col]=1;
    if(row==0&&col==0)
        go(v,row+1,col,tp+1);
    else
    {
        v[row][col]=0;
        bool l=false,r=false,u=false,d=false;
        if(ok(v,row,col+1))
            r=true;
        if(ok(v,row,col-1))
            l=true;
        if(ok(v,row+1,col))
            d=true;
        if(ok(v,row-1,col))
            u=true;
        if(!u&&!d&&r&&l)
            return;
        if(u&&d&&!r&&!l)
            return;
        v[row][col]=1;
        if(r)
            go(v,row,col+1,tp+1);
        if(l)
            go(v,row,col-1,tp+1);
        if(d)
            go(v,row+1,col,tp+1);
        if(u)
            go(v,row-1,col,tp+1);
    }
    v[row][col]=0;
}
void sol(ll cs)
{
    soln=0;
    cin>>N;
    vi<ll>temp(N,0);
    vi<vi<ll>>v(N,temp);
    go(v,0,0,1);
    cout<<csee<<2*soln<<"\n";
}
//CODE
int main()
{
    //freopen("inp.txt","r",stdin)
    scanf("%lld",&T);
    while(T--)
        sol(cs++);
    return 0;
}
content_copyCOPY