Untitled
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