Untitled
unknown
plain_text
5 months ago
1.6 kB
1
Indexable
Never
#include <iostream> #define N 101 #define oo 2000000009 using namespace std; int n,m; int a[N][N]; int d[N][N]; int ans; int dd[N][N]; void doc() { ans=0; n=7; m=8; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { dd[i][j]=0; cin>>a[i][j]; } for(int i=0;i<=6;i++) for(int j=i;j<=6;j++)d[i][j]=d[j][i]=0; for(int i=0;i<=n+1;i++)dd[i][0]=dd[i][m+1]=1; for(int j=1;j<=m;j++)dd[0][j]=d[n+1][j]=1; } void nhay(int i, int j, int &u, int &v) { if(j==m)u=i+1,v=1;else u=i,v=j+1; } void backtrack(int i,int j,int cnt) { if(i==n+1) { if(cnt==28)ans++; return; } if(dd[i][j]) { int u; int v; nhay(i,j,u,v); backtrack(u,v,cnt); } if(dd[i][j]==0) { if(dd[i][j+1]==0&&d[a[i][j]][a[i][j+1]]==0) { dd[i][j]=1; dd[i][j+1]=1; d[a[i][j]][a[i][j+1]]=1; d[a[i][j+1]][a[i][j]]=1; int u; int v; nhay(i,j,u,v); backtrack(u,v,cnt+1); dd[i][j]=0; dd[i][j+1]=0; d[a[i][j]][a[i][j+1]]=0; d[a[i][j+1]][a[i][j]]=0; } if(dd[i+1][j]==0&&d[a[i][j]][a[i+1][j]]==0) { dd[i][j]=1; dd[i+1][j]=1; d[a[i][j]][a[i+1][j]]=1; d[a[i+1][j]][a[i][j]]=1; int u; int v; nhay(i,j,u,v); backtrack(u,v,cnt+1); dd[i][j]=0; dd[i+1][j]=0; d[a[i][j]][a[i+1][j]]=0; d[a[i+1][j]][a[i][j]]=0; } } } int main() { //freopen("input.txt","r",stdin); int TC; cin>>TC; for(int tc=1;tc<=TC;tc++) { doc(); backtrack(1,1,0); cout<<"Case #"<<tc<<"\n"; cout<<ans<<"\n"; } return 0; }