UVa 211 - the Domino Effect(枚举+回溯)

多米诺骨牌每骨牌上有两个数,给出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博客 ,格式可能有所偏差。