domino

 avatar
duyvan
plain_text
6 months ago
1.6 kB
0
Indexable
Never
//domino

#include <iostream>

using namespace std;

int map[7][8];
int domino[7][8];
int visit[7][8];
int dx[] = {0,1};
int dy[] = {1,0};
int ans;

void backtrack(int x, int y){
    
    if(x == 7){
        ans++;
        return;
    }

    if(visit[x][y] == 0){
        for (int i = 0; i < 2; i++)
        {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(tx < 7 && ty < 8 && visit[tx][ty] == 0 && domino[map[x][y]][map[tx][ty]] == 0){
                    domino[map[x][y]][map[tx][ty]]= domino[map[tx][ty]][map[x][y]] = 1;
                    visit[x][y] = visit[tx][ty] = 1;
                    if(y<7){
                        backtrack(x,y+1);
                    }else
                    {
                        backtrack(x+1,0);
                    }
                    domino[map[x][y]][map[tx][ty]]= domino[map[tx][ty]][map[x][y]] = 0;
                    visit[x][y] = visit[tx][ty] = 0;
                }
            }
        }
    }else
    {
        if(y<7){
            backtrack(x,y+1);
        }else
        {
            backtrack(x+1,0);
        }
    }
}

int main(){
    
    int tc,T;
    freopen("input.txt", "r", stdin);
    cin>> T;
    for (tc = 1; tc <= T; tc++)
    {
        ans = 0;
        for (int i = 0; i < 7; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                cin>> map[i][j];
                domino[i][j] = 0;
                visit[i][j] = 0;
            }
        }
        backtrack(0,0);
        cout<<"#" << tc << " " << ans << endl;

    }

    return 0;
}
Leave a Comment