Untitled

mail@pastecode.io avatar
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;
}