[UVa] 1103 - Ancient Messages

這題的特點就是要採用三次的floodfill方法
1. 先將背景的白點floodfill轉換成'-'
2. 再找到黑點，並將黑點區域floodfill
3. 在上一個過程中如發現白點，則floodfill並計數

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int H,W;
char* hex2bin(char ch);
void dfs(int y, int x);
void dfs2(int y, int x);
void dfs3(int y, int x);
char image[210][210]; //image[y][x]
int count=0;
char result[100];
int main(){
    freopen("input.txt","r",stdin);
    int kase=0;
    while(scanf("%d %d",&H ,&W)!=EOF){
        if(H==0 && W==0)break;
        memset(image,0,sizeof(image));
        for(int i=0;i<100;i++)result[i]='\0';
        getchar();

        char input[60];
        for(int flag=0;flag<H;flag++){   
            int flag2=0; //轉為二進位時每一列使用的旗標
            fgets(input,sizeof(input),stdin);
            for(int i=0;i<sizeof(input);i++){
                char* s = hex2bin(input[i]); //s存放二進位
                for(int j=0;j<4;j++){
                    image[flag][flag2++]=s[j]; //s依序存入image的每一列
                }
            }
        }

        //dfs(0,0);
        //clear background
       
        for(int i=0;i<W*4;i++){
            if(image[0][i]=='0'){
                dfs(0,i);
            }
        }
        for(int i=0;i<W*4;i++){
            if(image[H-1][i]=='0'){
                dfs(H-1,i);
            }
        }
        for(int i=0;i<H;i++){
            if(image[i][0]=='0'){
                dfs(i,0);
            }
        }
        for(int i=0;i<H;i++){
            if(image[i][W*4-1]=='0'){
                dfs(i,W*4-1);
            }
        }
       
        /*
        //print whole image
        for(int i=0;i<H;i++){
            for(int j=0;j<W*4;j++){
                printf("%c",image[i][j]);
            }
                printf("\n");
        }
        */

        //put result into result[]
        int tmp=0;
        for(int i=0;i<H;i++){
            for(int j=0;j<W*4;j++){
                if(image[i][j]=='1'){
                    dfs2(i,j);
                    if(count==0)result[tmp]='W';
                    if(count==1)result[tmp]='A';
                    if(count==2)result[tmp]='K';
                    if(count==3)result[tmp]='J';
                    if(count==4)result[tmp]='S';
                    if(count==5)result[tmp]='D';
                    tmp++;
                    //printf("count = %d\n",count);
                    count = 0;
                }
            }
        }
       
        //sort the result in alpha
        for(int i=0;i<100 && result[i]!='\0' ;i++){
            for(int j=i+1;j<100 && result[j]!='\0' ;j++){
                if(result[i]>result[j]){
                    int t = result[i];
                    result[i] = result[j];
                    result[j] = t;
                }
            }
        }

    /*   
        //print whole image
        for(int i=0;i<H;i++){
            for(int j=0;j<W*4;j++){
                printf("%c",image[i][j]);
            }
                printf("\n");
        }
*/
        printf("Case %d: ",++kase);
      for(int i=0;i<100;i++){
            if(result[i]=='\0')break;
            printf("%c",result[i]);
        }
        printf("\n");
    }
    return 0;
}



// floodfill the background into '-'
void dfs(int y, int x){
    if(x<0 || x>=W*4 || y<0 || y>=H || image[y][x]!='0') return;
    if(image[y][x]=='0')image[y][x] = '-';
    dfs(y-1,x);
    if(y-1 >= 0 && image[y-1][x]=='0') dfs(y-1,x);
    if(y+1 < H && image[y+1][x]=='0') dfs(y+1,x);
    if(x-1 >= 0 && image[y][x-1]=='0') dfs(y,x-1);
    if(x+1 < W*4 && image[y][x+1]=='0') dfs(y,x+1);
}

// to count how many holes in each graph
void dfs2(int y, int x){
    if(x<0 || x>=W*4 || y<0 || y>=H || image[y][x]=='-') return;
    if(image[y][x]=='0'){
        dfs3(y,x);
        count++;
    }

    image[y][x]='-';
    if(y-1>=0)dfs2(y-1,x);
    if(y+1<H)dfs2(y+1,x);
    if(x-1>=0)dfs2(y,x-1);
    if(x+1<W*4)dfs2(y,x+1);
   
}
// floodfill the holes
void dfs3(int y, int x){
    if(x<0 || x>=W*4 || y<0 || y>=H || image[y][x]=='-') return;
    image[y][x]='-';
    if(y-1 >= 0 && image[y-1][x]=='0') dfs3(y-1,x);
    if(y+1 < H && image[y+1][x]=='0') dfs3(y+1,x);
    if(x-1 >= 0 && image[y][x-1]=='0') dfs3(y,x-1);
    if(x+1 < W*4 && image[y][x+1]=='0') dfs3(y,x+1);
}



//change hex to bin
char* hex2bin(char ch){
    static char bin[5]={0}, error[]="####";
    static char mask[4]={8,4,2,1};
    int i;
    if((ch>='0'&&ch<='9')||(ch>='A'&&ch<='F')||(ch>='a'&&ch<='f')){
        (ch-='0') > 10 ? ch-='7' : 0;
        for(i=0;i<4;i++) bin[i] = ch & mask[i] ? '1' : '0';
        return bin;
    }
    else return error;
}