UVA_657

首先可以用一个数组a[][]来存储图，其中“.”为-1，“*”为0，“X”为1。为了确保能把每个骰子都遍历完，我们可以使用两个判断是否访问的数组vis0[][]和vis1[][]，其中vis0为是否遍历过骰子上的点（包括X和*），由深搜函数dfs0使用，vis1表示是否在搜索X时搜过当前的X。

当我们遍历时候，如果遇到*或者X就进入dfs0，如果当前点为X时再跳入dfs1，每当在dfs0中跳入dfs1并跳出时，骰子的点数加1，当所有dfs0结束的时候，骰子数加1。

#include
     
       #include
      
        #include
       
         int a[60][60],vis0[60][60],vis1[60][60],num[60],n; char b[60]; int dx[]={
    -1,1,0,0},dy[]={
    0,0,-1,1}; int cmp(const void *_p,const void *_q) {
    int *p=(int *)_p; int *q=(int *)_q; return *p-*q; } void dfs1(int x,int y) {
    int i,newx,newy; for(i=0;i<4;i++)     {
            newx=x+dx[i];         newy=y+dy[i]; if(!vis1[newx][newy]&&a[newx][newy]==1)         {
                vis1[newx][newy]=1;             dfs1(newx,newy);         }     } } void dfs0(int x,int y) {
    int i,newx,newy; if(a[x][y]==1&&!vis1[x][y])     {
            vis1[x][y];         dfs1(x,y);         num[n]++;     } for(i=0;i<4;i++)     {
            newx=x+dx[i];         newy=y+dy[i]; if(a[newx][newy]!=-1&&!vis0[newx][newy])         {
                vis0[newx][newy]=1;             dfs0(newx,newy);         }     } } int main() {
    int i,j,k,r,c,t;     t=0; while(1)     {
            scanf("%d%d",&c,&r); if(r==0) break;         memset(a,-1,sizeof(a)); for(i=1;i<=r;i++)         {
                scanf("%s",b+1); for(j=1;j<=c;j++)             {
    if(b[j]=='*')                     a[i][j]=0; else if(b[j]=='X')                     a[i][j]=1;             }         }         n=0;         memset(num,0,sizeof(num));         memset(vis0,0,sizeof(vis0));         memset(vis1,0,sizeof(vis1)); for(i=1;i<=r;i++) for(j=1;j<=c;j++) if(a[i][j]!=-1&&!vis0[i][j])                 {
                        vis0[i][j]=1;                     dfs0(i,j);                     n++;                 }         qsort(num,n,sizeof(num[0]),cmp);         printf("Throw %d\n",++t); for(i=0;i