uva 657 The die is cast

解析圖 (travel graph)，實作時，比較難判斷的是遇到的 "X" 是否是和其他 "X" 相連，可能是從

其他方向走道 "X"，但是這是和之前走過的 "X" 相連。
 
我用的是兩個不同功能的 DFS，一個是用來把相連的 " *" 走完，一個是用來走完相連的一組

"X"，因為相連的 "X"，代表要被計算的點數值 1，但是走過的 "X" 要標上 "*"，前一個 DFS 才

能把這面 dice 走完。一次直接把連接的 "X" 走完，那下次遇到的 "X" 一定不是和之前遇到的

"X" 相連的，會比較好判斷。


test input:
3 2
XX*
X..
0 0

test output:
Throw 1
1
(newline)

(test input , output from : http://acm.uva.es/board/viewtopic.php?f=7&t=1948&hilit=657&sid=e5ead96b6830e0b0e7baed52294a391e&start=30#p204733)


#include <stdio.h>
#include <stdlib.h>

int counter;
int w,h;
char dice[60][60]={0};

void DFS_X(int x,int y){
    if(dice[x][y]!='X') return;

    dice[x][y]='*';

    DFS_X(x+1,y);
    DFS_X(x,y+1);
    DFS_X(x-1,y);
    DFS_X(x,y-1);

    return;
}

void DFS(int x, int y){
    if(dice[x][y]!='*' && dice[x][y]!='X') return;


    if(dice[x][y]=='X'){
        ++counter;
        DFS_X(x,y);
    }

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

    DFS(x+1,y);
    DFS(x,y+1);
    DFS(x-1,y);
    DFS(x,y-1);

    return;
}

int compare(const void*a, const void*b){
    return (*(int*)a)-(*(int*)b);
}

int main(void){
    int i,j;
    int num[100],top,cases=0;
    char c;

    while(scanf("%d%d%c",&w,&h,&c)==3){
        if(!w&&!h) break;

        for(i=1;i<=h;i++){
            for(j=1;j<=w;j++){
                scanf("%c",&dice[i][j]);
            }
            scanf("%c",&dice[i][j]);
        }

        top=-1;
        for(i=1;i<=h;i++){
            for(j=1;j<=w;j++){
                if(dice[i][j]=='*' || dice[i][j]=='X'){
                    counter=0;
                    DFS(i,j);
                    num[++top]=counter;
                }
            }
        }
        qsort(num,top+1,sizeof(int),compare);

        printf("Throw %d\n",++cases);
        for(i=0;i<top;i++){
            printf("%d ",num[i]);
        }
        printf("%d\n\n",num[i]);


    }


    return 0;
}