题目大意:给你7个正六边形,编号0 ~ 6 ,每个六边形的每条边的值均不同,且都是1 ~ 6 。让你按如下方式(a图)拼接:
拼接条件:
1、相邻两条边的值必须相同
2、位于中心的六边形的最上面的边的值必须为1
问这七个六边形能不能完成拼接,如果能,按b图示方式输出各个六边形的编号,即在0位置的先输出,然后输出在1位置的正六边形编号,以此类推。例如:如果编号为 3 的正六边形放在0位置,则先输出3 。
解题思路:只有7个正六边形,直接dfs暴搜回溯就ok了。
请看代码:
#include<iostream> #include<string> #include<algorithm> #include<cstring> #include<cmath> #include<cstdio> using namespace std ; int A[7] ; int s[8][6] ; int w[8][5] ; bool vis[10] ; int p1 ; int ca = 0 ; bool flag ; void init() { int i , j ; for(i = 0 ; i < 7 ; i ++) { for(j = 0 ; j < 6 ; j ++) { scanf("%d" , &s[i][j]) ; } } } void dfs(int step , int le , int r , int z) { int i ; if(step == 7) { flag = true ; for(i = 0 ; i < 7 ; i ++) { printf(" %d", A[i]) ; } puts("") ; return ; } for(i = 0 ; i < 7 ; i ++) { if(!vis[i]) { vis[i] = true ; int pr ; int j ; for(j = 0 ; j < 6 ; j ++) { if(s[i][j] == r) { pr = j ; break ; } } int tle , tr ; tle = s[i][(pr + 1) % 6] ; tr = s[i][pr] ; if(tle == le && tr == r) { A[step] = i ; if(step == 6) { if(pr == 0) { if(s[i][5] == z) dfs(step + 1 , s[i][5] , s[ A[0] ][(p1 + step) % 6] , z) ; } else { if(s[i][pr - 1] == z) dfs(step + 1 , s[i][pr - 1] , s[ A[0] ][(p1 + step) % 6] , z) ; } } else { if(pr == 0) { dfs(step + 1 , s[i][5] , s[ A[0] ][(p1 + step) % 6] , z) ; } else { dfs(step + 1 , s[i][pr - 1] , s[ A[0] ][(p1 + step) % 6] , z) ; } } } vis[i] = false ; } } } void solve() { memset(vis , 0 , sizeof(vis)) ; int i ; for(i = 0 ; i < 7 ; i ++) { vis[i] = true ; A[0] = i ; int j ; for(j = 0 ; j < 6 ; j ++) { if(s[i][j] == 1) { p1 = j ; break ; } } if(p1 == 0) w[0][0] = s[i][5] ; else w[0][0] = s[i][p1 - 1] ; w[0][1] = 1 ; w[0][2] = s[i][(p1 + 1) % 6] ; int k ; for(k = 0 ; k < 7 ; k ++) { if(!vis[k]) { vis[k] = true ; A[1] = k ; int pce ; for(int kk = 0 ; kk < 6 ; kk ++) { if(w[0][1] == s[k][kk]) { pce = kk ; break ; } } int zt ; int le , r ; zt = s[k][( pce + 1 ) % 6] ; if(pce == 0) le = s[k][5] ; else le = s[k][pce - 1] ; r = w[0][2] ; dfs(2 , le , r , zt) ; vis[k] = false ; } } vis[i] = false ; } if(flag == false) puts(" No solution") ; } int main() { int n ; scanf("%d" , &n) ; while (n --) { init() ; printf("Case %d:", ++ ca) ; flag = false ; solve() ; } return 0 ; }