Untitled

mail@pastecode.io avatarunknown
plain_text
25 days ago
1.8 kB
1
Indexable
Never
#include<iostream>
using namespace std;

int T;
int arr[7][8], domino[7][7], visit[7][8];
int rs;

void backtrack(int k) {
	int cot = k%8;
	int hang = k/8;

	if(k == 56) {
		rs ++;
		return;
	}
	if(visit[hang][cot]) {
		backtrack(k+1);
	}
	else {
		for(int i = 0; i < 2; i ++) {
			if(i == 0 && cot+1 >= 0 && cot+1 < 8 && domino[arr[hang][cot]][arr[hang][cot+1]] == 0 && visit[hang][cot+1] == 0) {
				int a = arr[hang][cot], b = arr[hang][cot+1];
				visit[hang][cot] = 1; visit[hang][cot+1] = 1;
				domino[a][b] = 1; domino[b][a] = 1;
				backtrack(k + 1);
				visit[hang][cot] = 0; visit[hang][cot+1] = 0;
				domino[a][b] = 0; domino[b][a] = 0;
			}
			else if(i == 1 && hang+1 >= 0 && hang+1 < 7 && domino[arr[hang][cot]][arr[hang+1][cot]] == 0 && visit[hang+1][cot] == 0) {
				int a = arr[hang][cot], b = arr[hang+1][cot];
				visit[hang][cot] = 1; visit[hang+1][cot] = 1;
				domino[a][b] = 1; domino[b][a] = 1;
				backtrack(k + 1);
				visit[hang][cot] = 0; visit[hang+1][cot] = 0;
				domino[a][b] = 0; domino[b][a] = 0;
			}
		}
	}

}

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> T;
	for(int test_case = 1; test_case <= T; test_case ++) {
		for(int i = 0; i < 7; i ++) {
			for(int j = 0; j < 8; j ++) {
				cin >> arr[i][j];
				visit[i][j] = 0;
			}
		}
		for(int i = 0; i < 7; i ++) {
			for(int j = 0; j < 7; j ++) {
				domino[i][j] = 0;
			}
		}
		rs = 0;
		backtrack(0);
		cout << "Case #" << test_case << endl << rs << endl;
	}
	return 0;
}

2

6 1 6 5 3 2 5 0

6 6 0 1 6 0 4 4

2 2 3 6 5 5 1 5

1 2 0 4 4 3 4 2

5 2 1 1 4 1 3 0

3 3 0 2 3 5 2 6

1 3 4 6 4 5 0 0

 

6 6 6 0 1 4 6 3

2 5 3 3 3 5 5 4

0 0 4 3 3 1 2 4

4 4 2 0 5 5 3 0

0 1 2 2 6 1 2 1

4 6 2 6 5 6 0 4

5 0 5 1 1 1 2 3

Case #1

32

Case #2

24