/** 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; }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter