程序设计大赛---多米诺效应

2024-01-10 14:33

本文主要是介绍程序设计大赛---多米诺效应,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

<!-- /* 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.

这篇关于程序设计大赛---多米诺效应的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/591125

相关文章

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型: 二、常量和变量 2.1常量和符号常量 在程序运行过程中,其值不能被改变的量称为常量。 常量区分为不同的类型: 程序中用#define(预处理器指令)命令行定义变量将代表常量,用一个标识符代表一个常量,称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元,用来存放数据,在程序运行期间,这些值是可以 改变的。 变

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①<(小于) ②<=(小于或等于) ③>(大于) ④>=(大于或等于 ) ⑤==(等于) ⑥!=(不等于) 说明: 前4个优先级相同,后2个优先级相同,关系运算符的优先级低于算术运算符,关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式(可以是算术表达式或关系表达式,逻辑表达式,赋值表达式,字符

智能工厂程序设计 之1 智能工厂都本俱的方面(Facet,Aspect和Respect)即智能依赖的基底Substrate 之1

Q1、昨天分别给出了三个智能工厂的 “面face”(里面inter-face,外面outer-face和表面surface) 以及每个“面face” 各自使用的“方”(StringProcessor,CaseFilter和ModeAdapter)  。今天我们将继续说说三个智能工厂的“方面” 。在展开之前先看一下三个单词:面向facing,取向oriented,朝向toword。理解这三个词 和

C语言程序设计 笔记代码梳理 重制版

前言 本篇以笔记为主的C语言详解,全篇一共十章内容,会持续更新基础内容,争取做到更详细。多一句没有,少一句不行!  形而上学者谓之道,形而下学者谓之器 形而上学者谓之道,形而下学者谓之器 第1章 C语言的流程 1.C程序经历的六个阶段 编辑(Edit)预处理(Preprocess)编译(Compile)汇编(Assemble)链接(Link)执行(Execute)  2.

ACM东北地区程序设计大赛

不得不说随着参赛级别的提高,题目真的是越来越难啊,不过队长真是给力啊,在我们三个共同努力之下拿下了地区赛三等奖,哈哈我们可是大一唯一一只获奖队,终于在这次比赛打败了田大神。。。大神是失手了,俺和他差距还是挺大的。。。队友陈彤马上要去服兵役了,他说这是我们送给他最好的离别礼物,希望那家伙在部队好好干,以后谁干揍我!!!东北地区赛结束后,今年已经估计没机会参加亚洲区比赛了,赶紧补高数和线数啊!!别挂了

pta-2024年秋面向对象程序设计实验一-java

文章申明:作者也为初学者,解答仅供参考,不一定是最优解; 一:7-1 sdut-sel-2 汽车超速罚款(选择结构) 答案: import java.util.Scanner;         public class Main { public static void main(String[] arg){         Scanner sc=new Scanner(System

C语言程序设计(算法的概念及其表示)

一、算法的概念 一个程序应包括两个方面的内容: 对数据的描述:数据结构 对操作的描述:算法 著名计算机科学家沃思提出一个公式: 数据结构 +算法 =程序 完整的程序设计应该是: 数据结构+算法+程序设计方法+语言工具 广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。 对同一个问题,可有不同的解题方法和步骤。为了有效地进行解题,不仅需要保证算法正确,还要考虑算

全国机器人大赛 Robocon 常州工学院团队首战国三

全国机器人大赛 Robocon 常州工学院团队首战国三 通宵7天7夜,常州工学院RC团队,首次闯入全国机器人大赛国赛,并成功得分! 不同于老牌强队,常州工学院(下面用"常工"代替)的这只队伍,大多数成员由大一组成,核心岗位由一些大二各个专业基础最为扎实的学生担任。 7月7日,19:26分。卡在报道的最后10分钟,由在团队项管和电控成功领队签到,光电Robot成为最近几年唯一一只冲入Roboc

UTON HACK 4.0 黑客马拉松大赛在马来西亚引起巨大反响

自第四届UTON HACK黑客马拉松大赛开启报名以来,吸引了全世界范围内区块链技术精英的广泛参与,在东南亚地区特别是马来西亚引起了巨大反响。 近日,马来西亚主流媒体Delight Media Malaysia对本次黑客马拉松大赛的协办单位马来西亚何氏全球总商会、UM公司进行了专访。 前排左一起是何致呈、何德成、何伟贤、尼克及马克。 (Delight Media Malaysia摄) 马来

1--程序设计的灵魂—算法

一:算法 特定问题求解步骤的描述 在计算机中表现为指令的有限序列 算法是独立存在的一种解决问题的方法和思想 对于算法而言,语言不重要,重要的是思想 二:算法特性 输入:有0个或多个输入 输出:至少一个输出 有穷:有限步骤之后自动结束 确定:每一步都有确定的含义 可行:每一步可行 三:算法设计准则 正确性,可读性,健壮性,高性价比 程序=数据结构+算法 四:影