Domino

 avatar
quoc14
c_cpp
17 days ago
10 kB
2
Indexable
Never
Backtrack
Level 4
Cover rectangle with dominos

Bạn được cung cấp 28 loại domino khác nhau, mỗi loại domino có kích thước 1x2 với 2 số trên đó như sau
0 0, 0 1, 0 2, 0 3, 0 4, 0 5, 0 6, 1 1, ..., 5 6, 6 6.

Và một bàn cờ có kích thước 7x8, nhiệm vụ của bạn là phủ kín bàn cờ bằng các quân domino sao cho chỉ có thể đặt một quân domino lên hai ô vuông liền kề trên bàn cờ nếu số ô vuông và số quân domino bằng nhau.

Có bao nhiêu cách khác nhau để che bảng?

Ví dụ nếu bảng được cho như bên dưới, có 18 cách để che nó, một trong số đó là như bên dưới.

Đầu vào

Dòng đầu tiên là số trường hợp thử nghiệm T (T < = 50).

Mỗi trường hợp thử nghiệm sẽ được đưa ra trên 7 dòng, mỗi dòng có 8 số cách nhau bởi một khoảng trắng là bảng cho trường hợp thử nghiệm. Có một dòng trống giữa 2 trường hợp thử nghiệm.

Đầu ra

In mỗi trường hợp kiểm tra trên hai dòng, dòng đầu tiên là "Trường hợp #x", trong đó x là số trường hợp kiểm tra, dòng tiếp theo là số hiệu của các cách phủ bảng khác nhau.

Sample

Input

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

...

 

Output

 

Case #1
32
Case #2
24

Case #1
66
Case #2
64
Case #3
58
Case #4
80
Case #5
26
Case #6
6
Case #7
112
Case #8
32
Case #9
900
Case #10
522
Case #11
24
Case #12
16
Case #13
132
Case #14
104
Case #15
90
Case #16
24
Case #17
18
Case #18
144
Case #19
144
Case #20
32
Case #21
12
Case #22
48
Case #23
144
Case #24
160
Case #25
48
Case #26
96
Case #27
100
Case #28
44
Case #29
108
Case #30
1638
Case #31
96
Case #32
64
Case #33
16
Case #34
160
Case #35
140
Case #36
90
Case #37
5
Case #38
18
Case #39
112
Case #40
76
Case #41
40
Case #42
96
Case #43
64
Case #44
64
Case #45
144
Case #46
5
Case #47
192
Case #48
72
Case #49
80
Case #50
72
Time: 0.203000000 s.
50
6 4 6 0 6 3 1 2 
6 1 5 3 5 0 4 0 
2 4 1 5 0 2 4 4 
5 5 1 3 6 5 4 1 
0 3 3 4 4 5 5 2 
2 3 2 6 1 1 0 1 
3 3 0 0 2 2 6 6 

3 3 3 2 6 6 4 6 
2 1 0 1 5 0 6 1 
4 1 4 3 0 4 0 2 
0 0 6 0 2 2 0 3 
3 1 5 2 2 4 3 5 
2 6 5 5 1 5 3 6 
5 4 4 4 6 5 1 1 

2 3 6 6 2 1 6 4 
1 3 2 2 5 4 3 4 
5 2 1 0 0 0 0 5 
4 4 1 1 5 3 6 3 
2 0 4 1 0 3 0 4 
2 6 6 1 0 6 2 4 
5 5 5 1 6 5 3 3 

0 0 1 3 2 6 0 6 
1 2 0 1 5 4 2 0 
0 4 1 4 4 6 1 6 
0 5 3 6 2 3 4 4 
5 6 5 5 5 2 0 3 
2 2 6 6 2 4 5 1 
3 4 1 1 3 3 5 3 

5 3 1 6 0 5 3 0 
4 2 1 4 4 3 6 2 
3 2 2 5 6 5 2 1 
2 0 1 0 1 1 3 6 
5 5 1 5 6 4 2 2 
0 4 4 5 6 6 6 0 
0 0 3 3 1 3 4 4 

2 0 1 5 0 5 5 4 
3 1 2 4 6 4 1 1 
1 2 3 6 5 2 3 0 
4 1 3 4 0 4 6 1 
6 6 3 2 0 6 5 6 
1 0 6 2 2 2 0 0 
5 3 5 5 4 4 3 3 

5 2 0 3 1 4 6 3 
5 1 3 2 6 0 0 4 
5 3 5 6 6 6 5 4 
6 4 4 4 1 0 1 1 
3 4 1 3 1 2 2 4 
2 2 6 1 2 0 5 0 
2 6 5 5 0 0 3 3 

5 6 2 5 2 6 4 3 
1 3 0 0 6 1 6 0 
3 5 5 4 0 2 1 5 
0 4 6 6 1 1 0 3 
6 4 3 2 0 1 1 2 
3 3 4 2 4 1 2 2 
0 5 5 5 4 4 3 6 

5 5 0 3 4 2 4 1 
1 5 2 0 6 5 5 0 
6 0 1 1 5 2 6 3 
4 6 3 2 2 2 6 6 
0 1 3 1 3 4 2 6 
0 4 3 3 5 4 1 2 
1 6 5 3 0 0 4 4 

6 2 5 2 5 5 4 1 
5 3 5 0 6 4 2 2 
3 6 1 6 1 2 0 2 
0 6 3 2 2 4 1 0 
4 5 4 3 6 6 5 1 
3 0 4 4 5 6 3 1 
3 3 0 4 1 1 0 0 

4 6 6 0 0 1 6 6 
0 0 2 4 0 3 5 6 
1 6 2 5 3 2 5 4 
4 0 1 4 3 4 2 0 
4 4 5 1 5 5 1 1 
3 6 0 5 2 1 2 2 
2 6 1 3 3 5 3 3 

3 1 0 3 1 5 1 1 
4 1 5 4 5 2 5 6 
6 0 0 2 3 2 4 3 
3 6 2 2 0 5 4 2 
5 5 1 0 0 4 3 5 
6 1 2 6 3 3 6 6 
2 1 4 6 0 0 4 4 

3 0 0 1 4 5 6 2 
6 3 2 0 2 2 1 1 
4 6 4 2 2 3 0 0 
5 2 1 4 5 0 1 3 
5 5 5 3 5 1 4 0 
6 0 5 6 4 4 2 1 
1 6 4 3 3 3 6 6 

2 4 4 5 0 4 0 3 
0 0 4 3 2 0 5 6 
3 6 3 2 6 6 2 6 
3 5 2 5 1 6 0 1 
4 4 2 1 0 6 6 4 
5 0 5 5 3 1 2 2 
4 1 1 5 1 1 3 3 

1 5 4 0 0 1 5 4 
1 4 2 2 5 3 6 1 
4 3 1 1 0 6 3 2 
4 4 1 3 0 2 2 4 
3 3 4 6 3 6 2 5 
5 6 0 0 2 1 6 6 
6 2 0 5 3 0 5 5 

4 6 5 2 0 2 0 0 
5 3 6 1 2 3 6 5 
5 1 1 2 2 4 6 3 
0 4 1 0 6 6 5 4 
1 4 6 0 3 3 6 2 
1 3 3 0 5 0 4 3 
5 5 1 1 2 2 4 4 

3 6 2 4 1 6 3 3 
4 0 1 5 2 2 4 1 
5 6 0 0 6 4 1 0 
1 3 5 3 6 6 2 0 
4 3 0 5 0 6 1 1 
5 2 2 6 1 2 2 3 
5 4 5 5 3 0 4 4 

5 6 3 6 6 0 4 0 
6 4 1 1 4 3 4 5 
3 3 2 0 1 2 2 4 
6 2 2 2 5 0 5 2 
3 1 2 3 3 5 4 4 
5 1 4 1 0 1 6 1 
0 3 5 5 0 0 6 6 

3 5 2 2 3 0 6 2 
0 4 5 1 3 2 3 1 
6 0 4 6 0 1 3 3 
6 1 0 0 1 1 5 4 
4 1 3 6 5 0 3 4 
5 6 1 2 0 2 4 4 
2 5 5 5 2 4 6 6 

2 5 3 1 0 5 0 3 
6 3 5 5 6 0 0 1 
4 1 3 5 4 4 2 1 
4 2 1 6 6 2 4 0 
2 2 1 5 3 4 2 0 
5 4 6 4 3 2 6 5 
1 1 0 0 3 3 6 6 

4 6 2 0 5 5 6 0 
5 6 5 2 0 0 4 3 
3 1 2 1 5 1 4 1 
3 5 0 3 2 2 6 3 
2 6 4 4 5 0 2 3 
2 4 1 1 1 0 6 6 
5 4 1 6 4 0 3 3 

1 1 0 4 5 1 3 5 
1 0 0 5 6 1 0 3 
5 2 4 4 4 6 0 2 
3 1 3 6 4 5 6 6 
6 2 3 2 3 3 2 2 
0 0 2 1 4 2 6 0 
3 4 5 6 1 4 5 5 

6 5 2 0 0 5 5 3 
6 2 1 2 1 6 4 0 
5 1 5 2 4 3 4 4 
1 4 2 2 6 3 4 5 
2 4 6 0 3 1 6 6 
3 0 6 4 1 1 1 0 
3 2 5 5 3 3 0 0 

6 2 1 5 0 6 6 4 
5 2 0 0 2 0 1 6 
4 4 4 5 0 5 0 1 
3 6 5 3 2 1 3 0 
3 2 2 2 4 2 3 1 
5 5 1 1 4 1 5 6 
4 0 4 3 6 6 3 3 

0 3 1 2 3 5 0 4 
5 4 3 2 6 1 1 0 
2 6 4 3 4 1 3 3 
3 1 5 0 6 6 0 6 
4 6 6 3 0 2 1 1 
2 2 5 2 0 0 5 6 
1 5 4 2 4 4 5 5 

1 0 5 4 6 3 2 2 
5 1 1 2 4 2 3 2 
3 4 0 6 4 6 3 5 
2 0 6 6 5 0 2 6 
6 5 3 3 2 5 1 6 
0 3 4 0 5 5 1 1 
1 4 0 0 1 3 4 4 

2 0 4 4 1 2 0 0 
2 4 2 2 6 0 6 3 
5 5 4 0 5 4 3 5 
3 3 1 3 1 6 5 2 
0 5 2 3 5 6 0 3 
6 6 2 6 6 4 1 4 
1 0 1 1 1 5 4 3 

6 5 4 0 2 4 3 1 
5 3 1 5 6 3 3 4 
5 4 6 4 3 3 2 5 
5 0 3 0 1 2 2 0 
4 4 1 0 2 6 3 2 
1 6 6 0 1 1 5 5 
0 0 4 1 6 6 2 2 

1 0 3 3 1 2 1 3 
5 5 3 5 5 1 2 4 
0 2 3 4 2 5 1 1 
3 0 6 4 0 0 4 5 
6 5 6 6 6 3 6 1 
3 2 6 2 0 5 0 6 
0 4 4 4 2 2 4 1 

4 0 6 3 6 1 0 3 
4 1 2 0 0 6 2 2 
5 2 1 5 6 5 5 5 
2 3 1 3 6 6 0 5 
3 4 2 1 6 4 4 5 
6 2 1 0 4 2 5 3 
3 3 0 0 4 4 1 1 

0 2 4 4 2 1 3 6 
3 5 6 6 1 3 4 1 
6 5 2 6 3 0 4 0 
1 5 2 3 6 1 2 2 
5 0 0 1 0 6 4 3 
4 2 1 1 2 5 6 4 
4 5 0 0 3 3 5 5 

2 3 0 4 6 6 2 6 
2 1 5 2 1 6 3 0 
0 5 0 6 5 6 5 4 
2 2 3 3 6 3 4 1 
6 4 1 0 0 0 5 5 
4 4 1 1 1 5 3 4 
3 1 0 2 2 4 5 3 

4 0 3 3 2 2 6 5 
3 0 4 6 4 3 0 2 
4 1 0 5 4 5 5 5 
6 6 0 6 3 6 3 1 
4 4 0 1 6 2 2 5 
3 5 1 2 1 1 2 4 
3 2 0 0 5 1 6 1 

6 1 2 3 6 0 6 4 
4 4 3 0 5 3 1 5 
1 2 3 1 6 2 1 1 
3 4 5 0 4 0 2 4 
6 3 5 6 5 4 0 2 
1 0 5 5 5 2 4 1 
6 6 3 3 2 2 0 0 

2 1 6 1 0 5 5 1 
4 0 0 3 4 2 6 3 
1 3 2 6 1 4 3 5 
1 0 0 0 5 2 4 3 
0 6 4 5 2 2 3 2 
2 0 6 4 5 6 6 6 
4 4 3 3 1 1 5 5 

1 0 0 5 1 2 3 1 
6 4 2 6 0 4 2 0 
3 3 4 2 4 5 3 2 
5 6 0 0 5 2 0 3 
6 0 3 5 3 6 4 1 
2 2 1 6 3 4 6 6 
5 5 4 4 1 5 1 1 

1 5 3 5 1 6 2 4 
4 4 4 3 0 0 0 4 
2 1 6 2 4 5 3 6 
2 3 0 2 0 5 0 6 
6 5 1 4 2 5 3 0 
1 1 2 2 1 3 4 6 
5 5 0 1 6 6 3 3 

0 1 5 5 6 0 2 4 
1 5 0 2 4 3 6 5 
5 3 4 0 1 3 6 1 
6 6 0 5 4 4 4 1 
0 3 1 1 2 6 0 0 
2 1 4 5 3 3 2 2 
3 6 2 3 6 4 2 5 

1 4 2 6 1 6 4 6 
6 5 3 4 0 3 0 2 
5 2 2 4 0 0 6 3 
5 0 4 4 1 1 6 0 
4 5 5 1 3 1 5 5 
3 5 1 0 1 2 2 2 
3 2 4 0 3 3 6 6 

1 6 0 6 4 0 0 2 
1 3 3 3 4 3 1 2 
5 5 0 3 3 2 4 5 
3 6 5 6 0 5 4 4 
1 4 5 1 1 0 0 0 
1 1 2 6 4 2 6 6 
5 3 2 5 4 6 2 2 

3 5 1 4 6 3 2 0 
2 3 0 5 1 3 4 0 
6 4 2 1 2 4 2 2 
1 0 0 0 4 3 5 6 
4 4 3 0 1 1 5 1 
5 2 5 5 6 2 0 6 
3 3 1 6 4 5 6 6 

6 0 0 5 6 1 5 2 
2 1 3 2 6 6 6 5 
4 1 4 0 1 0 5 4 
3 4 0 3 4 2 6 4 
2 2 2 0 6 3 3 5 
3 3 5 1 1 1 2 6 
1 3 4 4 5 5 0 0 

6 0 3 0 2 4 0 2 
1 5 3 3 4 4 5 3 
3 6 4 5 3 1 4 6 
6 5 2 5 1 0 5 0 
2 3 1 1 1 2 1 6 
2 2 6 2 1 4 0 0 
4 3 5 5 0 4 6 6 

0 3 6 5 3 2 5 3 
4 2 1 6 6 4 3 4 
1 0 1 4 5 4 0 5 
0 2 0 6 3 6 2 5 
6 6 1 3 2 2 1 5 
6 2 4 0 4 4 1 1 
3 3 0 0 1 2 5 5 

5 0 3 1 4 0 0 1 
2 0 2 2 6 1 2 6 
0 3 2 1 3 3 4 6 
1 5 3 5 3 4 0 6 
1 1 4 1 0 0 5 6 
2 5 4 2 5 4 6 6 
4 4 6 3 5 5 3 2 

0 5 6 4 1 0 0 0 
2 5 6 2 5 6 3 5 
4 3 4 2 3 6 0 4 
1 5 1 2 5 5 6 1 
1 3 1 1 2 3 3 3 
4 4 6 0 4 1 2 2 
6 6 2 0 4 5 0 3 

5 0 3 2 1 3 3 0 
6 5 5 4 3 6 1 4 
4 0 1 0 5 1 2 4 
0 2 5 5 0 0 5 3 
3 4 6 2 4 6 1 2 
3 3 6 6 0 6 2 5 
4 4 1 1 6 1 2 2 

4 1 4 0 5 6 6 4 
3 5 0 3 5 1 0 2 
6 1 4 5 0 6 3 1 
5 5 4 3 3 3 3 2 
2 6 5 0 2 1 1 1 
0 1 4 4 4 2 5 2 
6 6 3 6 2 2 0 0 

3 5 4 4 2 1 1 6 
1 4 4 0 3 4 4 5 
0 6 0 2 5 1 0 5 
3 6 2 5 5 5 2 6 
3 1 0 1 5 6 0 0 
3 2 2 2 0 3 6 4 
2 4 6 6 3 3 1 1 

2 4 4 5 1 2 6 3 
1 0 4 1 4 4 5 5 
2 2 6 1 0 0 5 0 
4 0 0 3 5 6 2 5 
6 4 1 3 1 5 3 3 
0 6 5 3 0 2 6 2 
3 2 3 4 1 1 6 6
    #include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, m = 8, n = 7, result; 
int vs[7][8], mp[7][8];
int have[7][8];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int maxx(int a, int b) { return (a>b ? a : b); }

int minn(int a, int b) { return (a<b ? a : b); }

bool inSide(int x, int y){ return x >= 0 && y >= 0 && x < n && y < m; }

void backtrack(int X, int Y, int cnt){
	if(X == n-1 && Y == m-1){
		if(cnt == 28) result++;
		return;
	}

	if(vs[X][Y]){
		int k = X*m + Y + 1;
		backtrack(k/m, k%m, cnt);
		return;
	}

	for(int d = 0; d < 4; d++){
		int xx = X + dx[d];
		int yy = Y + dy[d];
		if(inSide(xx, yy) && !vs[xx][yy]){
			
			int a = minn(mp[X][Y], mp[xx][yy]);
			int b = maxx(mp[X][Y], mp[xx][yy]);

			if(!have[a][b]){
				// vsTrue
				vs[X][Y]++;
				vs[xx][yy]++;
				have[a][b]++;

				int k = X*m + Y + 1;
				backtrack(k/m, k%m, cnt + 1);

				// vsFalse
				vs[X][Y]--;
				vs[xx][yy]--;
				have[a][b]--;
			}
		}
	}
}

int main(){

	freopen("input.txt", "r", stdin);

	// Calc clock
	clock_t time_start, time_end; 
	time_start = clock(); 
	
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Initial && Input
		result = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> mp[i][j];
				vs[i][j] = 0;
				have[i][j] = 0;
			}
		}

		// Solve Problem
		backtrack(0, 0, 0);
		
		// Output
		cout << "Case #" << tc << endl << result << endl;
	}

	// Calc Time
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(9);
	cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
	
	return 0;
 }
Leave a Comment