Domino
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