Untitled

 avatar
unknown
plain_text
a year ago
2.3 kB
4
Indexable
#include<iostream>

using namespace std;

int t,cnt;
int mang[7][8];
bool check[7][7];
bool visited[7][8];

void bt(int a){
	int r=a/8; int c=a%8;
	if(a==56){
		cnt++;
		return;
	}
	if(visited[r][c]) bt(a+1);
	else{
		if(c==7 && !check[mang[r][c]][mang[r+1][c]]){
			visited[r][c]=true; visited[r+1][c]=true;
			check[mang[r][c]][mang[r+1][c]]=check[mang[r+1][c]][mang[r][c]]=true;
			bt(a+1);
			visited[r][c]=false; visited[r+1][c]=false;
			check[mang[r][c]][mang[r+1][c]]=check[mang[r+1][c]][mang[r][c]]=false;
		}
		else if(r==6 && !visited[6][c+1] && !check[mang[6][c]][mang[6][c+1]]){
			visited[6][c]=true; visited[6][c+1]=true;
			check[mang[6][c]][mang[6][c+1]]=check[mang[6][c+1]][mang[6][c]]=true;
			bt(a+1);
			visited[6][c]=false; visited[6][c+1]=false;
			check[mang[6][c]][mang[6][c+1]]=check[mang[6][c+1]][mang[6][c]]=false;
		}
		else if(r<6 && c<7){
			if(visited[r][c+1] && !check[mang[r][c]][mang[r+1][c]]){
				visited[r][c]=true; visited[r+1][c]=true;
				check[mang[r][c]][mang[r+1][c]]=check[mang[r+1][c]][mang[r][c]]=true;
				bt(a+1);
				visited[r][c]=false; visited[r+1][c]=false;
				check[mang[r][c]][mang[r+1][c]]=check[mang[r+1][c]][mang[r][c]]=false;
			}
			else{
				for(int i=0;i<2;i++){
					if(i==0 && !check[mang[r][c]][mang[r][c+1]]){
						visited[r][c]=true; visited[r][c+1]=true;
						check[mang[r][c]][mang[r][c+1]]=check[mang[r][c+1]][mang[r][c]]=true;
						bt(a+1);
						visited[r][c]=false; visited[r][c+1]=false;
						check[mang[r][c]][mang[r][c+1]]=check[mang[r][c+1]][mang[r][c]]=false;
					}
					else if(i==1 && !check[mang[r][c]][mang[r+1][c]]){
						visited[r][c]=true; visited[r+1][c]=true;
						check[mang[r][c]][mang[r+1][c]]=check[mang[r+1][c]][mang[r][c]]=true;
						bt(a+1);
						visited[r][c]=false; visited[r+1][c]=false;
						check[mang[r][c]][mang[r+1][c]]=check[mang[r+1][c]][mang[r][c]]=false;
					}
				}
			}
		}
	}
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> t;
	for(int tc=1;tc<=t;tc++){
		for(int i=0;i<7;i++){
			for(int j=0;j<8;j++) {
				cin >> mang[i][j];
				visited[i][j]=false;
			}
		}
		for(int i=0;i<7;i++){
			for(int j=0;j<7;j++) check[i][j]=false;
		}

		cnt=0;
		bt(0);
		cout << cnt << endl;
	}

	return 0;
}
Editor is loading...
Leave a Comment