CoverRectangleWithDominos
ptrdung
plain_text
a year ago
10 kB
8
Indexable
You are given 28 different types of domino, each domino has size of 1x2 with 2 numbers on it as follow
(0,0), (0,1), (0,2),....., (0,6),
(1,1), (1,2),...,(1,6),
(2,2), (2,3),...,(2,6),
....
....
(5,5), (5,6),
(6,6).
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?
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 one line, the first is "#x", where x is the test case number, separate by a space and the numbers of different way to cover the board.
Sample
Input
5
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
2 4 0 2 6 6 4 1
4 5 6 0 3 5 5 6
0 1 6 3 4 3 3 2
0 3 1 1 5 1 3 1
2 5 0 0 6 2 3 3
4 0 6 4 5 0 5 5
2 1 4 4 2 2 6 1
0 5 4 4 2 5 6 2
3 5 1 1 1 0 4 1
3 1 5 1 4 3 1 6
2 0 6 4 5 5 5 6
3 3 3 0 2 3 2 1
0 0 6 0 6 3 4 5
4 2 6 6 0 4 2 2
3 0 6 5 6 4 1 0
3 5 1 3 1 1 0 2
4 4 5 4 3 3 3 2
5 5 1 4 5 1 6 0
5 0 2 2 2 1 6 3
3 4 0 0 6 6 2 5
1 6 4 2 0 4 6 2
Output
#1 32
#2 24
#3 40
#4 16
#5 20
#include <iostream>
using namespace std;
int T;
int map[7][8], visited[7][8];
int a[28], b[28], c[28];
int Count = 0;
int x=0, y=0;
int used[7][7];
bool isLastCell(int x, int y) {
if ((x == 6 ) && ( y == 7)) return true;
return false;
}
bool isVisited(int x, int y) {
if (visited[x][y] == 1) return true;
return false;
}
bool isUsed(int number1, int number2) {
if (used[number1][number2] == 1) return true;
return false;
}
void setUsed(int number1, int number2){
used[number1][number2] = 1;
used[number2][number1] = 1;
}
void setVisitedX(int x, int y) {
visited[x][y] = 1;
visited[x+1][y] = 1;
}
void setVisitedY(int x, int y) {
visited[x][y] = 1;
visited[x][y+1] = 1;
}
void resetUsed(int number1, int number2) {
used[number1][number2] = 0;
used[number2][number1] = 0;
}
void resetVisitedX(int x, int y) {
visited[x][y] = 0;
visited[x+1][y] = 0;
}
void resetVisitedY(int x, int y) {
visited[x][y] = 0;
visited[x][y+1] = 0;
}
void BT(int x, int y) {
if (isLastCell(x, y)) {
Count++; //cout << " afajhfjhgk" << endl;
}
else if (!isVisited(x, y)) {
//duoi
if ((x < 6) && !isVisited(x+1, y)) {
int number1 = map[x][y];
int number2 = map[x+1][y];
if (!isUsed(number1, number2)) {
setUsed(number1, number2);
setVisitedX(x, y);
if (y < 7) BT(x, y+1);
else BT(x+1, 0);
resetUsed(number1, number2);
resetVisitedX(x, y);
}
}
//ngang
if ((y < 7) && !isVisited(x, y+1)) {
int number1 = map[x][y];
int number2 = map[x][y+1];
if (!isUsed(number1, number2)) {
setUsed(number1, number2);
setVisitedY(x, y);
if (y < 7) BT(x, y+1);
else BT(x+1, 0);
resetUsed(number1, number2);
resetVisitedY(x, y);
}
}
} else
{
if (y < 7) BT(x, y+1);
else
{
BT(x+1,0);
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
cin >> T;
for (int tc = 1; tc <= T; tc++) {
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 8; j++) {
cin >> map[i][j];
visited[i][j] = 0;
//cout << map[i][j] << " ";
}
//cout << endl;
}
BT(0,0);
cout <<"#" << tc << " " << Count << endl;
Count = 0;
}
//while(1);
return 0;
}
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 6Editor is loading...
Leave a Comment