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; }
Leave a Comment