題目：The Domino Effect

題意：有一副牌，給出pips和bone的對應值。現在輸入一個7*8的pips矩陣，輸出所有對應的bone矩陣。bone矩陣是每倆個相同數字是挨著的。

思路：自己搞了半天后還是參考了別人了，其實還是標準dfs回溯，只不過位置是一個一個移動的枚舉的。

（1）枚舉：從位置（0,0）開始，每個位置有倆個方向：下或右，每次進行y+1即坐標向右移動一位，當到達邊界時將x+1，y=0即移到下一行開始位置繼續，直到28個數全部放完為止。

（2）搜索：判斷如果當前位置有數字了就繼續搜索下一位置，否則進行倆個方向的枚舉，將當前位置和枚舉的位置放在給出的表里查找得出bone值，然后看bone值是否使用過，沒有使用即當前位置和枚舉位置放入其bone值即可，然后繼續搜索下一位置，否則不搜索繼續枚舉。

注意：每個案例結果直接空3行，否則直接WA，不提示PE！！！

參考：JeraKrs博客

代碼：

#include <stdio.h>#include <string.h>#define ms(a) memset(a,0,sizeof(a))const int maxn = 10;int pips[maxn][maxn],bone[maxn][maxn];int table[maxn][maxn];int dx[] = {0,1};int dy[] = {1,0};int visit[30],ans;bool input(){    for(int i=0;i<7;i++)            for(int j=0;j<8;j++) if(scanf("%d",&pips[i][j]) != 1) return false;    return true;}void init(){//將給出的表格保存到數組里。    int num = 1;    for(int i=0;i<7;i++)        for(int j=i;j<7;j++)            table[i][j] = table[j][i] = num++;}void put(int a[][maxn]){    for(int i=0;i<7;i++){        for(int j=0;j<8;j++) PRintf("%4d",a[i][j]);printf("/n");    }printf("/n");}void dfs(int x,int y,int steps){    if(steps == 28){//當28個數字全部填充完時說明排好了        ans++;put(bone);        return;    }    if(y == 8){//換行        x++;y = 0;    }    if(bone[x][y]) dfs(x,y+1,steps);//當本位置編號時進行遞歸下一位置    else{        for(int i=0;i<2;i++){//倆個位置：下和右            int tx = x + dx[i], ty = y + dy[i];            if(tx >= 7 || ty >= 8 || bone[tx][ty]) continue;//超出范圍或此位置有編號了            int tem = table[pips[x][y]][pips[tx][ty]];//將上一位置的pips和下方或右方的對應的bone找到            if(visit[tem]) continue;//是否此編號使用過            visit[tem] = 1;bone[x][y] = bone[tx][ty] = tem;//將倆位置放入其中            dfs(x,y+1,steps+1);//移動一格繼續            bone[x][y] = bone[tx][ty] = 0;visit[tem] = 0;//回溯        }    }}int main(){    int kcase = 0;    init();    while(input()){        if(kcase) printf("/n/n/n");        printf("Layout #%d:/n/n",++kcase);        put(pips);        printf("Maps resulting from layout #%d are:/n/n",kcase);        ms(visit);ms(bone);ans = 0;        dfs(0,0,0);        printf("There are %d solution(s) for layout #%d./n",ans,kcase);    }    return 0;}