题目简括
给出一张16进制表示的位图，要求按2进制识别出图中象形文字，象形文字一共有6种(下图)。将识别出来的所有象形文字按其对应字母排序后输出。
对应字母：
Ankh: A
Wedjat: J
Djed: D
Scarab: S
Was: W
Akhet: K
条件：
两个象形文字不会重叠以及相接；
象形文字可能会水平或垂直拉伸，但不会裂成两部分；
位图中每个有效黑像素点(‘1’)都算是一个象形文字的部分。
思路
首先将16进制位图转换为2进制的位图。
然后这题直接扫描黑像素点判断不了是什么文字，观察发现，6个文字的内部白色快的数量是不同的，分别是：A->1, J->3, D->5, S->4, W->0, K->2，利用这个识别出文字。
我的做法是先将外部白色区域染色，这样剩下的所有白色区域均处于文字内部，这时扫描文字，单一个文字的任意像素与白色区域邻接时，将此白色区域染色，然后计数+1，最终可以得到文字内部的白色快数量。然后储存结果，排序后输出即可。
要注意的是，文字可能邻接位图边缘，所以需要给位图加一个白色边框，保证第一个染色点是外部区域。
扫描黑色文字时，总的像素点较少，可以用DFS，不会爆栈。
染色外部区域时，因为外部区域面积可能很大，所以需要用全局队列进行BFS，还有不能使用STL的queue，会超时。
测试用例：1103 | uDebug
AC代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
struct node{
int x, y;
} arr[60010];
struct queue{
int h, t;void pop(){
++h; }void push(int x, int y){
arr[t].x = x;arr[t].y = y;++t;}bool empty(){
return h == t; }
} q;
int book[210][210];
char g2[210][60];
char g[210][210];
char hex[16][5];
char hieroglyphs[7] = "WAKJSD";
char sign[41000], len;
int dx[] = {
-1, 0, 1, 0};
int dy[] = {
0, 1, 0, -1};
int n, m;
void convert(int r, int c){
//16进制位图转2进制for(int i = 0; i < r; i++){
g[i + 1][0] = '0';int k = 1;for(int j = 0; j < c; j++){
int k2;if(g2[i][j] < 'a') k2 = g2[i][j] - '0';else k2 = g2[i][j] - 'a' + 10;for(int r = 0; r < 4; r++)g[i + 1][k++] = hex[k2][r];}g[i + 1][k] = '0';g[i + 1][k + 1] = '\0';}for(int i = 0; i < m; i++)g[0][i] = g[n - 1][i] = '0';g[0][m] = g[n - 1][m] = '\0';
}
void init(){
//预先储存哈希值char code[5];for(int i = 0; i < 16; i++){
for(int j = 0; j < 4; j++)if(i & (1 << j))code[3 - j] = '1';else code[3 - j] = '0';code[5] = '\0';strcpy(hex[i], code);}
}
bool isValid(int x, int y){
return x >= 0 && y >= 0 && x < n && y < m;
}
void floodfill_white(int x, int y, char c1, char c2){
//队列BFSq.h = q.t = 0;q.push(x, y);memset(book, 0, sizeof(book));book[x][y] = 1;while(!q.empty()){
int kx = arr[q.h].x;int ky = arr[q.h].y;q.pop();g[kx][ky] = c2;for(int i = 0; i < 4; i++){
int nx = kx + dx[i];int ny = ky + dy[i];if(isValid(nx, ny) && g[nx][ny] == c1 && book[nx][ny] == 0)book[nx][ny] = 1, q.push(nx, ny);}}
}
int floodfill_black(int x, int y, char c1, char c2){
//DFS扫描文字g[x][y] = c2;int ans = 0;for(int i = 0; i < 4; i++){
int nx = x + dx[i];int ny = y + dy[i];if(isValid(nx, ny)){
if(g[nx][ny] == '0')//某个像素点邻接有白色++ans, floodfill_white(nx, ny, '0', 'w');else if(g[nx][ny] == '1')ans += floodfill_black(nx, ny, c1, c2);}}return ans;
}
int main(){
init();int r, c, t = 1;while(scanf("%d%d", &r, &c), (r || c)){
getchar();for(int i = 0; i < r; i++)gets(g2[i]);n = r + 2;m = c * 4 + 2;convert(r, c);//转换floodfill_white(0, 0, '0', 'w');//外部区域染色len = 0;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)if(g[i][j] == '1'){
int white_size = floodfill_black(i, j, '1', 'b');//扫描文字并得到内部白色块数量sign[len++] = hieroglyphs[white_size];}std::sort(sign, sign + len);//排序结果sign[len] = '\0';printf("Case %d: %s\n", t++, sign);}
}