uva 1103 Ancient Messages (古象形文字)

象形文字)"/>

uva 1103 Ancient Messages (古象形文字)

题意：以十六进制的形式给出图像，求所给图像中图像所表示的字母。

思路：先建立十六进制对应二进制索引表，输入的时候建立二进制表。需要两次DFS，第一次DFS去掉图像周围的边界部分（既将图像外二进制为0的部分变成其他符号,便于第二次DFS的时候跳过这些边界。这里我用'-'代表被裁掉的边界）,第二次DFS，查找图像的边界，一旦找到边界就开始DFS，并将边界所相邻的内0通过第一次的DFS方法变成'-'，表示这个图像的内空洞已经找到，并将计数变量cnt++。当最后根据cnt的值来判断所对应的字母。

import java.util.Arrays;
import java.util.Scanner;public class Main {static char[] index = {'A','D','J','K','S','W'};static int[] num = new int[6];static String[] bin = {"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};static int[] dr = {-1,0,0,1};static int[] dc = {0,1,-1,0};static int[][] tab = new int[256][256];static int H,W;static int cnt;public static void main(String[] args) {Scanner scan = new Scanner(System.in);int kcases = 1;while(true){Arrays.fill(num, 0);H = scan.nextInt();W = scan.nextInt();if(H==0||W==0)break;W*=4;for(int i=0;i<H;i++){String str = scan.next();int cnt = 0;for(int j=0;j<str.length();j++){int cp = str.charAt(j);if(cp>=48&&cp<=57)cp -=48;else cp=cp - 97+10;//System.out.println(bin[cp]);//System.out.println(cp);for(int k=0;k<bin[cp].length();k++){tab[i][cnt++] = bin[cp].charAt(k)-'0';}}}//处理边界for(int i=0;i<H;i++){if(tab[i][0]==0)DFS1(i,0);if(tab[i][W-1]==0)DFS1(i,W-1);}for(int i=0;i<W;i++){if(tab[0][i]==0)DFS1(0,i);if(tab[H-1][i]==0)DFS1(H-1,i);}//扫描图形for(int i=0;i<H;i++){for(int j=0;j<W;j++){if(tab[i][j]==1){cnt = 0;DFS2(i,j);if(cnt==0) num[5]++;  if(cnt==1) num[0]++;  if(cnt==2) num[3]++;  if(cnt==3) num[2]++;  if(cnt==4) num[4]++;  if(cnt==5) num[1]++;}}}System.out.printf("Case %d: ",kcases++);for(int i=0;i<6;i++){for(int j=0;j<num[i];j++){System.out.print(index[i]);}}System.out.println();}}public static boolean isIn(int r,int c){return r>=0&&r<H&&c>=0&&c<W;}public static void DFS1(int r,int c){if(!isIn(r,c)||tab[r][c]!=0)return;tab[r][c] = '-';for(int i=0;i<4;i++){DFS1(r+dr[i],c+dc[i]);}}public static void DFS2(int r,int c){if(!isIn(r,c)||tab[r][c]!=1)return;tab[r][c] = '-';for(int i=0;i<4;i++){int r1 = r+dr[i];int c1 = c+dc[i];if(isIn(r1,c1)&&tab[r1][c1]==0){cnt++;DFS1(r1,c1);}DFS2(r1,c1);}}
}