注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

UVA The die is cast  

2012-07-01 21:52:57|  分类: 数据结构基础 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description


  The die is cast 

InterGames is a high-tech startup company that specializes in developing technology that allows users to play games over the Internet. A market analysis has alerted them to the fact that games of chance are pretty popular among their potential customers. Be it Monopoly, ludo or backgammon, most of these games involve throwing dice at some stage of the game.

Of course, it would be unreasonable if players were allowed to throw their dice and then enter the result into the computer, since cheating would be way to easy. So, instead, InterGames has decided to supply their users with a camera that takes a picture of the thrown dice, analyzes the picture and then transmits the outcome of the throw automatically.

For this they desperately need a program that, given an image containing several dice, determines the numbers of dots on the dice.

We make the following assumptions about the input images. The images contain only three dif- ferent pixel values: for the background, the dice and the dots on the dice. We consider two pixels connected if they share an edge - meeting at a corner is not enough. In the figure, pixels A and B are connected, but B and C are not.

UVA The die is cast - Minary - Minary_Acdream

A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence $a_1, a_2, \dots, a_k$ in S such that a = a1 and b = ak, and ai and ai+1 are connected for $1 \le i < k$.

We consider all maximally connected sets consisting solely of non-background pixels to be dice. `Maximally connected' means that you cannot add any other non-background pixels to the set without making it dis-connected. Likewise we consider every maximal connected set of dot pixels to form a dot.

Input 

The input consists of pictures of several dice throws. Each picture description starts with a line containing two numbers w and h, the width and height of the picture, respectively. These values satisfy $5 \le?w,h \le 50$.

The following h lines contain w characters each. The characters can be: ``.'' for a background pixel, ``*'' for a pixel of a die, and ``X'' for a pixel of a die's dot.

Dice may have different sizes and not be entirely square due to optical distortion. The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive.

The input is terminated by a picture starting with w = h = 0, which should not be processed.

Output 

For each throw of dice, first output its number. Then output the number of dots on the dice in the picture, sorted in increasing order.

Print a blank line after each test case.

Sample Input 

30 15 .............................. .............................. ...............*.............. ...*****......****............ ...*X***.....**X***........... ...*****....***X**............ ...***X*.....****............. ...*****.......*.............. .............................. ........***........******..... .......**X****.....*X**X*..... ......*******......******..... .....****X**.......*X**X*..... ........***........******..... .............................. 0 0 

Sample Output 

Throw 1 1 2 2 4 

=  =这题WA了许久许久许久

第一遍发现需要两个endl,第二遍,第三遍,第四遍一直在找特殊情况下的数据。

结果,发现,没有把文件给注释掉...

注释掉后就AC了 =。 =

真粗心//

 

思路很简单,两个DFS就可以了

注意的是每次都要把数组清空。

下面是我的代码

 

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n,m;
char map[300][300];
int dir[4][2]  = {{1,0},{0,-1},{-1,0},{0,1}};
int co[1000];
int t = 0;
int N = 1;

void DFS1(int x,int y)
{
 int xx,yy;
 map[x][y] = '*';
 for(int i=0;i<4;i++)
    {
        xx=x+dir[i][0];
        yy=y+dir[i][1];
        if(xx >= n || yy >= m || xx < 0 || yy < 0)
        continue;
        if(map[xx][yy] == 'X')
        DFS1(xx,yy);
    }
 
}

void DFS(int x,int y)
{
    int i,xx,yy;
    map[x][y]='.';
    for(i=0;i<4;i++)
    {
        xx=x+dir[i][0];
        yy=y+dir[i][1];
        if(xx >= n || yy >= m || xx < 0 || yy < 0)
        continue;
        if(map[xx][yy] == 'X' )
  {
   DFS1(xx,yy);
   co[t] ++;
   
  }
        if(map[xx][yy] == '*' )
        DFS(xx,yy);
    }
}


int main()
{

   while(~scanf("%d%d",&m,&n))
    {
     int i,j;
   
     if(n == 0 && m == 0) break;
        cin.get();
       
        for(i = 0;i < n;i ++)
        {
            for(j = 0;j < m;j ++)
            scanf("%c",&map[i][j]);
            cin.get();
        }
       
        for(i = 0;i <= n;i++)
        {
            for(j = 0;j <= m;j++)
            {
                if(map[i][j] == '*')
                {
                    DFS(i,j);//从(i,j)位置进行DFS;
                    t ++;
                     }
            }
        }
        sort(co,co+t);   co[t] = 0;
           
   
cout<<"Throw "<<N<<endl;   N ++;
for(int i = 0;i < t - 1 ;i ++)   cout<<co[i]<<" ";
      
cout<<co[t-1]<<endl<<endl;
  memset(co,0,sizeof(co)) ;
        t = 0;
     
    }
    return 0;
}


  评论这张
 
阅读(163)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018