UVa 211 - The Domino Effect（枚举＋回溯）

发表于 分类于 ， Disqus：

多米诺骨牌每骨牌上有两个数，给出7*8的数表，问如何用骨牌布满，输出所有可能解。

一共只有28个骨牌，一开始就感觉是暴力的问题。

首先预处理骨牌，因为每个骨牌都可以用唯一的数对表示，所以用二维数组g来储存对应骨牌的编号。

然后从左上角开始进行枚举，vis储存状态。当存在骨牌冲突时回溯，当右下角也铺上骨牌时输出当前解。

PS：貌似lay和dfs能够和在一起写，但是感觉分开代码会短一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=10;
int lo[maxn][maxn],vis[maxn][maxn],g[maxn][maxn],cnt;
bool used[30];
void prepare(){//处理骨牌。
    for(int i=1,j=0,k=0;i<=28;++i,++k){
        if(k>6) ++j,k=j;
        g[j][k]=g[k][j]=i;
    }
    return;
}
bool read(){
    for(int i=0;i<7;++i)
        for(int j=0;j<8;++j)
            if(scanf("%d",&lo[i][j])==EOF) return false;
    return true;
}
void dfs(int);
void lay(int x,int y,bool right,int cur){//铺骨牌，变量right控制向下铺还是向右铺。
    int x1=x,y1=y;
    if(right) ++y1;
    else ++x1;
    int a=lo[x][y],b=lo[x1][y1];
    if(g[a][b]&&!used[g[a][b]]){
        used[g[a][b]]=true;
        vis[x][y]=vis[x1][y1]=g[a][b];
        dfs(cur+1);//<span style="font-family: Arial, Helvetica, sans-serif;">两个函数互相递归调用。</span>
        used[g[a][b]]=false;
        vis[x][y]=vis[x1][y1]=-1;
    }
    return;
}
void dfs(int cur){
    if(cur==28){//铺满打印解。
        for(int i=0;i<7;++i){
            for(int j=0;j<8;++j)
                printf("%4d",vis[i][j]);
            printf("\n");
        }
        printf("\n");
        ++cnt;
        return;
    }
    int x=7,y=8;
    for(int i=0;i<7;++i){
        bool flag=true;
        for(int j=0;j<8;++j)
            if(vis[i][j]==-1){
                flag=false;
                x=i,y=j;
                break;
            }
        if(!flag) break;
    }
    if(y+1<8&&vis[x][y+1]==-1) lay(x,y,true,cur);//两个函数互相递归调用。
    if(x+1<7&&vis[x+1][y]==-1) lay(x,y,false,cur);
    return;
}
int solve(){
    cnt=0;
    memset(vis,-1,sizeof(vis));
    memset(used,0,sizeof(used));
    dfs(0);
    return cnt;
}
int main(){
    int t=0;
    prepare();
    while(read()){
        if(t) printf("\n\n\n");
        printf("Layout #%d:\n\n",++t);
        for(int i=0;i<7;++i){
            for(int j=0;j<8;++j)
                printf("%4d",lo[i][j]);
            printf("\n");
        }
        printf("\nMaps resulting from layout #%d are:\n\n",t);
        printf("There are %d solution(s) for layout #%d.\n",solve(),t);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章