# domino

duyvan
plain_text
21 days ago
1.7 kB
0
Indexable
Never
```#include<iostream>
#define endl '\n'
using namespace std;

int map[8][9];
int visit[8][9];
int ans;
bool domino[7][7];

void input()
{
for(int i = 0; i < 7; ++i)
for(int j = 0; j < 8; ++j)
cin >> map[i][j];
}

void init_domino()
{
for(int i = 0; i < 7; ++i)
for(int j = 0; j < 7; ++j)
domino[i][j] = 1;
}

bool check (int x, int y, int nx, int ny)
{
if(domino[map[x][y]][map[nx][ny]])	return true;
return false;
}

void backtrack(int x, int y)
{
if(y == 8 && x == 6)	{ans++;	return;}
if(y == 8 && x != 6)	{backtrack(x+1,0); return;}	//Neu o ria duyet ngang ma x chua end -> xuong dong
if(visit[x][y] == 1)	{backtrack(x,y+1); return;}	//Neu o visit -> duyet ngang

visit[x][y] = 1;
if(y + 1 < 8 && visit[x][y+1] == 0 && check(x,y,x,y+1))	//check xem backtrack ngang duoc khong
{
visit[x][y+1] = 1;
domino[map[x][y]][map[x][y+1]] = 0;
domino[map[x][y+1]][map[x][y]] = 0;
backtrack(x,y+2);
domino[map[x][y+1]][map[x][y]] = 1;
domino[map[x][y]][map[x][y+1]] = 1;
visit[x][y+1] = 0;
}

if(x + 1 < 7 && visit[x+1][y] == 0 && check(x,y,x+1,y))	//check xem backtrack ngang duoc khong
{
visit[x+1][y] = 1;
domino[map[x][y]][map[x+1][y]] = 0;
domino[map[x+1][y]][map[x][y]] = 0;
backtrack(x,y+1);
domino[map[x][y]][map[x+1][y]] = 1;
domino[map[x+1][y]][map[x][y]] = 1;
visit[x+1][y] = 0;
}
visit[x][y] = 0;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int T;
cin >> T;
for(int tc = 1; tc <= T; ++tc)
{
ans = 0;
input();
init_domino();
backtrack(0,0);

cout << "#" << tc << " " << ans << endl;
}

return 0;
}```