UVa 657 掷骰子

意甲冠军：有一个大图。每个像素是格孩子只可能是 . * X 三种。代表背景、玻色子、色子点。

两格子是邻近或在通信，当且仅当两个格儿子*要么X。且具有共同的边，这是上下左右四个方向，斜过，即四连块。

个色子。将这个连通块中的X的连通块个数看做该色子的点数。

思路：两次深搜。第一次是由*和X来深搜每一个连通块。在深搜每一个连通块时由X来深搜X的连通块个数。这里能够通过两个标记数组visit来表示是否訪问过，visitx来表示是否訪问深搜X过。（也能够将X改为*、*改为.的方式实现，不用标记数组。之前我想的是用一个标记数组，然后对其值的推断来实现，不如两个标记数组来得简便和直观）

注意：在主函数的两个for循环进行深搜前。注意推断是否已訪问过，否则产生大量点数为0的色子。另外，由于这个循环每次成功去深搜都是深搜了一个大的连通块，所以色子个数的添加应该在这个循环里，不要放在dfs里~

（之前的思路是。深搜一次。*在深搜时遇到X则点数加1，X深搜时遇到X则点数不加。

发现对2行2列的数据*XXX就会出错。由于这样算一个，那个思路算出来的是两个。

之后看了网上的思路，參考了一下。两次深搜，学习了~）

这里的深搜都是标记其被訪问过，每次深搜都是标记完一个连通块。

然后统计了訪问的次数，即连通块的个数：色子数、色子的点数。（包含之前油田那题的深搜也是这样。）

inclusive 包括的，exclusive才是排他的~

这里通过用字符 . 来初始化图G，并从1而不是0開始，即在图外围围了一圈字符 . ，这样就可避免推断坐标是否出界。（加一圈外围的停止字符，避免推断坐标是否出界）

Code：

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define MAXN 55

int cmp_int(const void *_a, const void *_b);

void dfs(int hs,int ls);

void dfsx(int hs,int ls);

int w,h;

char G[MAXN][MAXN];

int visit[MAXN][MAXN];

int visitx[MAXN][MAXN];

int dir[][4]={{-1,1,0,0},{0,0,1,-1}};//LRDU。前x后y，前水平后竖直

int num[MAXN*MAXN];//对应色子的点数

int cnt;//色子个数

int main()

{

 //freopen("657.in","r",stdin);

 //freopen("657.out","w",stdout);

 int thrw=1;

 while(scanf("%d%d",&w,&h) && w && h)

 {

  memset(G,'.',sizeof(G));

  memset(visit,0,sizeof(visit));

  memset(visitx,0,sizeof(visitx));

  for(int i=1;i<=h;++i)

  {

   getchar();

   for(int j=1;j<=w;++j)

   {

    G[i][j]=getchar();

   }

  }

  cnt=0;

  memset(num,0,sizeof(num));

  for(int i=1;i<=h;++i)

   for(int j=1;j<=w;++j)

    if(G[i][j]!='.' && !visit[i][j])//注意这里的!visit条件。不然会打出非常多点数为0的色子

    {

     dfs(i,j);

     cnt++;//色子数添加            //注意这个别放在dfs语句中了，想一想就理解了

     //printf("%d %d\n",i,j);

    }

  qsort(num,cnt,sizeof(num[0]),cmp_int);

  printf("Throw %d\n",thrw++);

  for(int i=0;i<cnt;++i)

   if(i==0) printf("%d",num[i]);

   else printf(" %d",num[i]);

  printf("\n\n");

 }

 return 0;

}

int cmp_int(const void *_a, const void *_b)

{

 return *(int*)_a-*(int*)_b;

}

void dfsx(int hs,int ls)

{//由X来遍历连通块

 if(G[hs][ls]!='X' || visitx[hs][ls]) return ;

 visitx[hs][ls]=1;

 for(int i=0;i<4;++i)

 {

  int nh=hs+dir[1][i];

  int nl=ls+dir[0][i];

  dfsx(nh,nl);

 }

}

void dfs(int hs,int ls)

{//从一点出发，由*和X来遍历连通块

 if(G[hs][ls]=='.' || visit[hs][ls]) return ;

 visit[hs][ls]=1;

 if(G[hs][ls]=='X' && !visitx[hs][ls])

 {

  dfsx(hs,ls);

  num[cnt]++;//点数添加

 }

 //else if(G[hs][ls]=='*')            //注意这里别加这个推断条件。由于就算是字符X也须要进行以下这个循环的遍历

  for(int i=0;i<4;++i)

  {

   int nh=hs+dir[1][i];

   int nl=ls+dir[0][i];

   dfs(nh,nl);

  }

}