本题就是灵活运用DFS来求连通块来求解的。
题意：
给出一幅黑白图像，每行相邻的四个点压缩成一个十六进制的字符。然后还有题中图示的6中古老的字符，按字母表顺序输出这些字符的标号。
分析:
首先图像是被压缩过的，所以我们要把它解码成一个01矩阵。而且我们还要在原图像的四周加一圈白边，这样图中的白色背景都连通起来了。
黑色连通块的个数就是字符的个数。
观察题中字符样式可知，每种字符中包裹的“白洞”的个数是不同的，所以我们可以根据每个字符中的“白洞”的个数来区别这些字符。
然后我们给所有的连通块染色，并用color存储所标记的颜色。第一个染的是白色背景色，编号为1
把所有的黑色连通块的标号存放到cc里面
neighbors是由若干个集合所组成的数组，记录的是黑色连通块i周围相连的非背景色的白块，即“白洞”。
最后每个集合中元素的个数对应的就是字符的编号，最后排序输出即可。
一个DEBUG很久的低级错误：在DFS的时候忘了加 color[row2][col2] == 0 这一判断条件，相当于没有回溯了，当然会栈溢出，RE。这里的color顺带也起到了表示是否访问过的作用。
//#define LOCAL
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
using namespace std; const int maxl = + ;
char bin[][], s[maxl];
const int dr[] = { , , -, };
const int dc[] = { , , , - };
int picture[maxl][maxl], color[maxl][maxl], w, h; vector<set<int> > neighbor; void decode(int row, int col, char c)
{
for(int i = ; i < ; ++i)
picture[row][col + i] = bin[c][i] - '';
} bool inside(int row, int col)
{
return row>= && row<h && col>= && col<w;
} void DFS(int row, int col, int c)
{
color[row][col] = c;
for(int i = ; i < ; ++i)
{
int row2 = row + dr[i];
int col2 = col + dc[i];
if(inside(row2, col2) && picture[row][col] == picture[row2][col2] && color[row2][col2] == )
DFS(row2, col2, c);
}
} void check_neighbor(int row, int col)
{
for(int i = ; i < ; ++i)
{
int row2 = row + dr[i];
int col2 = col + dc[i];
if(row2>= && row2<h && col2>= && col2<w && picture[row2][col2] == && color[row2][col2] != )//寻找"洞"
neighbor[color[row][col]].insert(color[row2][col2]);
}
} const char* code = "WAKJSD"; char recgonize(int c)
{
int a = neighbor[c].size();
return code[a];
} int main(void)
{
#ifdef LOCAL
freopen("1103in.txt", "r", stdin);
#endif strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin[''], "");
strcpy(bin['a'], "");
strcpy(bin['b'], "");
strcpy(bin['c'], "");
strcpy(bin['d'], "");
strcpy(bin['e'], "");
strcpy(bin['f'], ""); int kase = ;
while(scanf("%d%d", &h, &w) == && h)
{
memset(picture, , sizeof(picture));
for(int i = ; i < h; ++i)
{
scanf("%s", s);
for(int j = ; j < w; ++j)
decode(i+, j*+, s[j]);
} h += ;
w = w * + ; int cnt = ;
vector<int> cc;
memset(color, , sizeof(color));
for(int i = ; i < h; ++i)
for(int j = ; j < w; ++j)
if(!color[i][j])
{
DFS(i, j, ++cnt);
if(picture[i][j] == ) cc.push_back(cnt);
} neighbor.clear();
neighbor.resize(cnt + );
for(int i = ; i < h; ++i)
for(int j = ; j < w; ++j)
if(picture[i][j] == )
check_neighbor(i, j); vector<char> ans;
for(int i = ; i < cc.size(); ++i)
ans.push_back(recgonize(cc[i]));
sort(ans.begin(), ans.end()); printf("Case %d: ", ++kase);
for(int i = ; i < ans.size(); ++i) printf("%c", ans[i]);
printf("\n");
} return ;
}
代码君