Domino
quoc14
c_cpp
5 months ago
10 kB
3
Indexable
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