两次DFS，POJ(1481)

题目链接：http://poj.org/problem?id=1481

两次DFS，这里的思路是，没找到*，就说明，有一个骰子，因此，每搜索到一个*，深搜4个方向，并且变为'.'，要是搜到'X'，就是骰子的点数++，而且将他的四周的'X'变为'.'

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<string>

using namespace std;

char a[+][+];

int count;

int i_cmp(void const *x,void const *y)

{

    return *(int*)x-*(int*)y;

}

void DFS_X(int x,int y)

{

    if(a[x][y]!='X')

        return ;

    else

        a[x][y]='.';

    DFS_X(x-,y);    ///题目要求只需要考虑上下左右四个方向即可，而不是八个方向

    DFS_X(x,y-);

    DFS_X(x,y+);

    DFS_X(x+,y);

}

void DFS(int x,int y)

{

    if(a[x][y]=='.')

        return ;

    if(a[x][y]=='X')

    {

        DFS_X(x,y);

        count++;

    }

    a[x][y]='.';

    DFS(x-,y);

    DFS(x,y-);

    DFS(x,y+);

    DFS(x+,y);

}

int main()

{

    int w,h,num=,ct,dote[];

    while(scanf("%d%d",&w,&h)!=EOF)

    {

        if(w==&&h==) break;

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

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

        {

            getchar();

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

                scanf("%c",&a[i][j]);

        }

        ct=;

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

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

                if(a[i][j]=='*')

                {

                    count=;

                    DFS(i,j);

                    dote[ct++]=count;

                }

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

        qsort(dote,ct,sizeof(dote[]),i_cmp);

        for(int i=; i<ct; i++)

        {

            if(i)

                printf(" ");

            printf("%d",dote[i]);

        }

        printf("\n\n");

    }

    return ;

}