Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
9.0 kB
0
Indexable
Never
Cover rectangle with dominos
You are given 28 different types of domino, each domino has size of 1x2 with 2 numbers on it as follow



And a board of size 7x8, your task is cover the board with above dominos such that a domino can only be placed on two adjacent squares on board if the numbers of the squares and of domino are equal.

How many different way to cover the board?

For example if the board are given as below, there are 18 way to cover it, one of them is as below.







Input

The first line is the number of test case T (T < = 50).

Each test case will be given on 7 lines, each line have 8 numbers separate by a space is the board for the test case. It have a empty line between 2 test cases.

Output

Print each test case on two lines, the first line is "Case #x", where x is the test case number, the next line is the numbers of different way to cover the board.

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

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>
using namespace std;

int n = 7, m = 8;
int arr[8][9];
int dR[2] = {0, 1};
int dC[2] = {1, 0};
int dd[8][9];
int dem;
int dd1[8][9];

void BackTrack(int i, int j){
	if(i == n){
		dem++;
		return;
	}

	if(dd[i][j] == 0){

		int d1 = arr[i][j];

		for(int k=0; k<2; k++){
			int x = i + dR[k];
			int y = j + dC[k];

			if(x>=0 && x<n && y>=0 && y<m && dd[x][y] == 0){

				int d2 = arr[x][y];

				int dmin = min(d1, d2);
				int dmax = max(d1, d2);

				if(dd1[dmin][dmax] == 0){

					dd[i][j] = 1;
					dd[x][y] = 1;
					dd1[dmin][dmax] = 1;

					if(j<m-1)
						BackTrack(i, j+1);
					else
						BackTrack(i+1, 0);
					//BackTrack(i,j);
					dd1[dmin][dmax] = 0;
					dd[x][y] = 0;
					dd[i][j] = 0;

				}
			}
		}
	}else{

		if(j<m-1)
			BackTrack(i, j+1);
		else
			BackTrack(i+1, 0);

	}

}

int main(){
	//freopen("vao.txt", "r", stdin);
	int t;
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				cin >> arr[i][j];
			}
		}

		dem = 0;

		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				dd[i][j] = 0;
				dd1[i][j] = 0;
			}
		}

		BackTrack(0, 0);

		cout << "Case #" << tc << endl;

		cout << dem << endl;
	}
	return 0;
}