Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.2 kB
3
Indexable
Never
#include <iostream>

using namespace std;

int arr[8][9];
int N = 7, M = 8;
int T;
int cnt;
int visited[8][9];
int X[2] = {0, 1};
int Y[2] = {1, 0};
int check[8][9];
int tmp;

void backtrack(int k){
	if(k == 56){
		cnt++;
		return;
	}
	int x = k / 8;
	int y = k % 8;

	int a = arr[x][y];

	if(check[x][y] == 0){
		for(int i = 0; i < 2; i++){
			int row = x + X[i];
			int col = y + Y[i];
			if(row >= 0 && row < N && col >= 0 && col < M && check[row][col] == 0){

				int b = arr[row][col];

				if(visited[a][b] == 0){

					check[row][col] = 1;
					visited[a][b] = 1;
					visited[b][a] = 1;

					backtrack(k + 1);

					check[row][col] = 0;
					visited[a][b] = 0;
					visited[b][a] = 0;
				}
			}
		}
	}else{
		backtrack(k + 1);
	}
}

int main(){
	freopen("input.txt", "rt", 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 >> arr[i][j];
				visited[i][j] = 0;
				check[i][j] = 0;
			}
		}
		cnt = 0;
		tmp = 0;
		backtrack(0);
		cout << "Case #" << tc << endl;
		cout << cnt << endl;
	}
	while(1);
	return 0;
}
Leave a Comment