Uva211 The Domino Effect 【dfs回溯】【习题7-3】

题目：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;}