本文主要是介绍程序设计大赛---多米诺效应，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
<!-- /* Font Definitions */ @font-face {font-family:宋体; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-alt:SimSun; mso-font-charset:134; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 135135232 16 0 262145 0;} @font-face {font-family:"/@宋体"; panose-1:2 1 6 0 3 1 1 1 1 1; mso-font-charset:134; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 135135232 16 0 262145 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0cm; margin-bottom:.0001pt; text-align:justify; text-justify:inter-ideograph; mso-pagination:none; font-size:10.5pt; mso-bidi-font-size:12.0pt; font-family:"Times New Roman"; mso-fareast-font-family:宋体; mso-font-kerning:1.0pt;} /* Page Definitions */ @page {mso-page-border-surround-header:no; mso-page-border-surround-footer:no;} @page Section1 {size:612.0pt 792.0pt; margin:72.0pt 90.0pt 72.0pt 90.0pt; mso-header-margin:36.0pt; mso-footer-margin:36.0pt; mso-paper-source:0;} div.Section1 {page:Section1;} -->
一副标准的“双六”多米诺骨牌共有 28 张，每张用类似于股子的点数表示两个从 0 到 6 的骨牌。这 28 张不同的骨牌由以下点数的组合构成：
骨牌 # 点数
1 0|0
2 0|1
3 0|2
4 0|3
5 0|4
6 0|5
7 0|6
8 1|1
9 1|2
10 1|3
11 1|4
12 1|5
13 1|6
14 2|2
15 2|3
16 2|4
17 2|5
18 2|6
19 3|3
20 3|4
21 3|5
22 3|6
23 4|4
24 4|5
25 4|6
26 5|5
27 5|6
28 6|6
用一副“双六”多米诺骨牌的所有可以被拼成一个 7*8 的点数网格。每种拼法至少对应一副多米诺骨牌的“图”。一副图由一个合适的骨牌号替换在该骨牌上的点数而确定 7*8 的网格组成。下面是一个 7*8 的点数网格以及一个相应的骨牌号图。
7*8 点数网格
6 6 2 6 5 2 4 1
1 3 2 0 1 0 3 4
1 3 2 4 6 6 5 4
1 0 4 3 2 1 1 2
5 1 3 6 0 4 5 5
5 5 4 0 2 6 0 3
6 0 5 3 4 2 0 3
骨牌的图
28 28 14 7 17 17 11 11
10 10 14 7 2 2 21 23
8 4 16 25 25 13 21 23
8 4 16 15 15 13 9 9
12 12 22 22 5 5 26 26
27 6 24 3 3 18 1 19
27 6 24 20 20 18 1 19
输入：
输入文件包含一些包括一些测试项。每项由 7 行每行 8 个在 0 到 6 之间的整数组成，代表所看到的点数网格。每个测试项对应一个合法的骨牌放置方案（每个测试项至少有一个可能的图）。在各测试项之间没有分割数据。
输出：
正确的输出包括一个测试项编号（从 #1 开始），接下来是测试本身。在这之后是这个测试项的图的标号及对应于测试项的图（若多于一个图可按照任意次序输出）。当一个测试项的所有图多输出完后，一个总计行应当给出所有可能的图的总数。各测试项的输出之间应有 2 个空行，同一个测试项的标号、测试项本身和图之间应有一个空行隔开。
我的程序：
/***************************************************
程序名：多米诺效应（骨牌）
作者：许文发
时间： 2009-11-26
***************************************************/
#include<iostream.h>
#include<stdio.h>
#include<string.h>
int first=1;// 首次输出
int start; // 每组首次输出结果
int solution;// 每组解数
// 获取骨牌数
int gupaiNum(int m,int n)
{
int temp,sum=0,result;
if(m>n)
{
temp=m;
m=n;
n=temp;
}
for(int i=1;i<=m;i++)
{
sum+=i;
}
result=m*7-sum+n+1;
return result;
}
// 是否成功，返回 1 表示全不为 0 ，否则返回 0
int sussess(int gupai[][8])
{
int i,j;
int result=1;
for(i=0;i<7;i++)
{
for(j=0;j<8;j++)
{
if(gupai[i][j]==0)
result=0;
}
}
return result;
}
// 清文件
void clearfile()
{
FILE *pt;
pt=fopen("output.txt","w");
fclose(pt);
}
// 输入输出
void myprint(int domino[][8],int num)
{
FILE *pt;
int line_first;
pt=fopen("output.txt","a");
int i,j;
if(!first)
{
fprintf(pt,"/n/n");
}
fprintf(pt,"Layout #%d/n/n",num);
for(i=0;i<7;i++)
{
line_first=1;
for(j=0;j<8;j++)
{
if(line_first)
fprintf(pt,"%2d",domino[i][j]);
else
fprintf(pt," %2d",domino[i][j]);
line_first=0;
}
fprintf(pt,"/n");
}
fclose(pt);
}
// 结果输出
void mywrite(int gupai[][8],int num)
{
FILE *pt;
int line_first;
pt=fopen("output.txt","a");
int i,j;
if(start)
fprintf(pt,"/nMaps resulting from layout #%d are:/n/n",num);
else
fprintf(pt,"/n/n");
for(i=0;i<6;i++)
{
line_first=1;
for(j=0;j<8;j++)
{
if(line_first)
fprintf(pt,"%2d",gupai[i][j]);
else
fprintf(pt," %2d",gupai[i][j]);
line_first=0;
}
fprintf(pt,"/n");
}
line_first=1;
for(j=0;j<8;j++)
{
if(line_first)
fprintf(pt,"%2d",gupai[6][j]);
else
fprintf(pt," %2d",gupai[6][j]);
line_first=0;
}
fclose(pt);
}
// 判断数字 n 是否存在于数组 gupai
int isExist(int gupai[][8],int n)
{
int result=0;
int i;
for(i=0;i<7*8;i++)
{
if(gupai[i/8][i%8]==n)
{
result=1;
break;
}
}
return result;
}
// 回溯
void group(int domino[][8],int gupai[][8],int dir[][2],int num)
{
int i,j,k;
int n1,n2;
int count;
int n;
int tempNum;
if(sussess(gupai))
{
mywrite(gupai,num++);
start=0;
solution++;
}
else
{
for(n=0;n<7*8;n++)
{
i=n/8;
j=n%8;
if(gupai[i][j]==0)
{
count=0;
for(k=0;k<4;k++)
{
count++;
n1=i+dir[k][0];
n2=j+dir[k][1];
if(n1>=0 && n1<=6 && n2>=0 && n2<=7 && gupai[n1][n2]==0)
{
tempNum=gupaiNum(domino[i][j],domino[n1][n2]);
if(!isExist(gupai,tempNum))
{
gupai[i][j]=tempNum;
gupai[n1][n2]=tempNum;
group(domino,gupai,dir,num);
gupai[i][j]=0;
gupai[n1][n2]=0;
}
}
}
if(count==4)
break;
}
}
}
}
// 输出最后一行 There are n solution(s) for layout
void last(int solution,int num)
{
FILE *pt;
pt=fopen("output.txt","a");
fprintf(pt,"/nThere are %d solution(s) for layout #%d.",solution,num);
fclose(pt);
}
void main()
{
clearfile();
FILE *pt;
int domino[7][8];// 输入
int gupai[7][8]; // 输出
int dir[4][2]={-1,0,0,-1,1,0,0,1};// 方向
int i,n;
int total; // 总数
int temp;
int num=1; // 组序列数
if(NULL==(pt=fopen("input.txt","r")))
{
cout<<"can't open the input.txt"<<endl;
}
else
{
total=0;
while(fscanf(pt,"%d",&temp)!=EOF)
{
total++;
}
rewind(pt);
for(n=0;n<total/56;n++)
{
start=1;
solution=0;
for(i=0;i<7*8;i++)
{
fscanf(pt,"%d",&domino[i/8][i%8]);
}
myprint(domino,num);
memset(gupai,0,sizeof(gupai));
group(domino,gupai,dir,num);
last(solution,num);
first=0;
num++;
}
fclose(pt);
}
}
输入：
5 4 3 6 5 3 4 6
0 6 0 1 2 3 1 1
3 2 6 5 0 4 2 0
5 3 6 2 3 2 0 6
4 0 4 1 0 0 4 1
5 2 2 4 4 1 6 5
5 5 3 6 1 2 3 1
6 6 2 6 5 2 4 1
1 3 2 0 1 0 3 4
1 3 2 4 6 6 5 4
1 0 4 3 2 1 1 2
5 1 3 6 0 4 5 5
5 5 4 0 2 6 0 3
6 0 5 3 4 2 0 3
4 2 5 2 6 3 5 4
5 0 4 3 1 4 1 1
1 2 3 0 2 2 2 2
1 4 0 1 3 5 6 5
4 0 6 0 3 6 6 5
4 0 1 6 4 0 3 0
6 5 3 6 2 1 5 3
输出：
Layout #1
5 4 3 6 5 3 4 6
0 6 0 1 2 3 1 1
3 2 6 5 0 4 2 0
5 3 6 2 3 2 0 6
4 0 4 1 0 0 4 1
5 2 2 4 4 1 6 5
5 5 3 6 1 2 3 1
Maps resulting from layout #1 are:
6 20 20 27 27 19 25 25
6 18 2 2 3 19 8 8
21 18 28 17 3 16 16 7
21 4 28 17 15 15 5 7
24 4 11 11 1 1 5 12
24 14 14 23 23 13 13 12
26 26 22 22 9 9 10 10
There are 1 solution(s) for layout #1.
Layout #2
6 6 2 6 5 2 4 1
1 3 2 0 1 0 3 4
1 3 2 4 6 6 5 4
1 0 4 3 2 1 1 2
5 1 3 6 0 4 5 5
5 5 4 0 2 6 0 3
6 0 5 3 4 2 0 3
Maps resulting from layout #2 are:
28 28 14 7 17 17 11 11
10 10 14 7 2 2 21 23
8 4 16 25 25 13 21 23
8 4 16 15 15 13 9 9
12 12 22 22 5 5 26 26
27 6 24 3 3 18 1 19
27 6 24 20 20 18 1 19
28 28 14 7 17 17 11 11
10 10 14 7 2 2 21 23
8 4 16 25 25 13 21 23
8 4 16 15 15 13 9 9
12 12 22 22 5 5 26 26
27 24 24 3 3 18 1 19
27 6 6 20 20 18 1 19
28 28 14 7 17 17 11 11
10 10 14 7 2 2 21 23
8 15 15 20 18 13 21 23
8 5 5 20 18 13 9 9
12 12 22 22 3 25 26 26
27 6 24 4 3 25 1 19
27 6 24 4 16 16 1 19
28 28 14 7 17 17 11 11
10 10 14 7 2 2 21 23
8 15 15 20 18 13 21 23
8 5 5 20 18 13 9 9
12 12 22 22 3 25 26 26
27 24 24 4 3 25 1 19
27 6 6 4 16 16 1 19
There are 4 solution(s) for layout #2.
Layout #3
4 2 5 2 6 3 5 4
5 0 4 3 1 4 1 1
1 2 3 0 2 2 2 2
1 4 0 1 3 5 6 5
4 0 6 0 3 6 6 5
4 0 1 6 4 0 3 0
6 5 3 6 2 1 5 3
Maps resulting from layout #3 are:
16 16 24 18 18 20 12 11
6 6 24 10 10 20 12 11
8 15 15 3 3 17 14 14
8 5 5 2 19 17 28 26
23 1 13 2 19 7 28 26
23 1 13 25 25 7 21 4
27 27 22 22 9 9 21 4
16 16 24 18 18 20 12 11
6 6 24 10 10 20 12 11
8 15 15 3 3 17 14 14
8 5 5 2 19 17 28 26
23 1 13 2 19 7 28 26
23 1 13 25 25 7 4 4
27 27 22 22 9 9 21 21
There are 2 solution(s) for layout #3.
这篇关于程序设计大赛---多米诺效应的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
