SGU 101 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=101

101. Domino

time limit per test: 0.50 sec.
memory limit per test: 4096 KB

Dominoes – game played with small, rectangular blocks of wood or other material, each identified by a number of dots, or pips, on its face. The blocks usually are called bones, dominoes, or pieces and sometimes men,stones, or even cards.
The face of each piece is divided, by a line or ridge, into two squares, each of which is marked as would be a pair of dice...

The principle in nearly all modern dominoes games is to match one end of a piece to another that is identically or reciprocally numbered.

ENCYCLOPÆDIA BRITANNICA

多米诺 – 一种使用木头或其他材料制作的方块进行的游戏。方块的每个面上标记上确定的数字或点。方块常常被称做骨,骨牌或片,有时使用人,骨头或卡片进行.

每个骨牌的面使用一条线分成两部分,每个部分标记一个数字.

几乎所有现代骨牌游戏的原则是:骨牌数字相同的部分首位相接,最后连成串.

–––––– 《大英百科全书》

Given a set of domino pieces where each side is marked with two digits from 0 to 6. Your task is to arrange pieces in a line such way, that they touch through equal marked sides. It is possible to rotate pieces changing left and right side.

给定一系列两端标记为0~6数字的骨牌.你的任务是排列这些骨牌,使他们相接触的部分数字相同,你可以左右翻转骨牌.

Input

The first line of the input contains a single integer N (1 ≤ N ≤ 100) representing the total number of pieces in the domino set. The following N lines describe pieces. Each piece is represented on a separate line in a form of two digits from 0 to 6 separated by a space.

第一行输入一个整数 N (1 ≤ N ≤ 100) 代表骨牌的数量. 接下来 N 行代表 N 块骨牌. 每块骨牌使用两个0~6的使用空格隔开的数字表示.

Output

Write “No solution” if it is impossible to arrange them described way. If it is possible, write any of way. Pieces must be written in left-to-right order. Every of N lines must contains number of current domino piece and sign “+” or “-“ (first means that you not rotate that piece, and second if you rotate it).

如果无法将骨牌连成串,则输出"No solution". 否则输出任何一种符合条件的排列方案.输出是从左到右描述骨牌的排列.每行包含一个数字和一个符号,分别表示骨牌的编号和是否翻转骨牌,(+表示不翻转,-表示翻转)。

Sample Input

5
1 2
2 4
2 4
6 4
2 1

Sample Output

2 -
5 +
1 +
3 +
4 -

这道题总算让我好好理解了一下dfs.

因为骨牌上数字的范围很小,只有0~6,所以采用矩阵的邻接表来表示骨牌,数组元素的数值代表骨牌的数量.

题目的实质就是问能否找一条欧拉路将所有边走一遍.

首先找到度数为奇数的点,作为起点,如果没有,则任取一个点作为起点.如果度数为奇数的点不是2个(一个起点一个终点)或0个(形成环)那肯定无解.

然后进行深度优先搜索.需要注意的是,如果可以将所有骨牌连在一起,那深搜肯定是一搜到底不会出现回溯的问题.深搜过程中使用一个ans数组记录搜索过程中经过的边.

最后再判断ans数组的元素个数就可以了.至于输出什么的,看代码就知道了.

CODE

#include<stdio.h>
#include<string.h>
 
struct node
{
  int x,y;
}ans[202],dom[202];
 
int k,D[7][7],deg[7];
 
void dfs(int s)
{
  int i;
  for(i=0;i<7;++i)
    if(D[s][i])
      {
	--D[s][i];
	--D[i][s];
	dfs(i);
	++k;
	ans[k].x=s;
	ans[k].y=i;
      }
}
 
int main()
{
  int i,j,n,x,y;
  scanf("%d",&n);
  memset(D,0,sizeof(D));
  memset(deg,0,sizeof(deg));
  for(i=1;i<=n;++i)
    {
      scanf("%d%d",&x,&y);
      ++D[x][y];
      ++D[y][x];
      ++deg[x];
      ++deg[y];
      dom[i].x=x;
      dom[i].y=y;
    }
  for(i=0;i<7;++i)
    {
      if(deg[i])
	{
	  j=i;
	  break;
	}
    }
  k=0;
  for(i=0;i<7;++i)
    {
      if(deg[i]%2)
	{
	  ++k;
	  j=i;
	}
    }
  if(!(k==0||k==2))
    {
      printf("No solutionn");
      return 0;
    }
  k=0;
  dfs(j);
  if(k!=n)
    {
      printf("No solutionn");
      return 0;
    }
  for(i=k;i>0;--i)
    for(j=1;j<=n;++j)
      if(ans[i].x==dom[j].x && ans[i].y==dom[j].y)
	{
	  printf("%d +n",j);
	  dom[j].x=-1;
	  break;
	}
      else if(ans[i].x==dom[j].y && ans[i].y==dom[j].x)
	{
	  printf("%d -n",j);
	  dom[j].x=-1;
	  break;
	}
  return 0;
}
» 本博客采用署名 2.5 中国大陆许可协议进行许可,本文版权归作者所有,欢迎转载,但必须在明显位置给出原文连接。
anyShare分享到:
发表评论?

0 条评论。

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>