题目链接:http://vjudge.net/contest/140550#problem/B
紫书P163.
1、根据16进制图转成2进制图。
每个点dfs一下,马上就把最外围的连通分量编号求出来了为1,这个不是文字里面的空白。
2、求每个文字,四周的空白有多少。——用一个set容器,当你查看这个像素为1 的点,发现四周的点的连通分量编号不同并且不是 1 ,就可以插入到 set 中,set 防止重复。然后这种像素点为 1 对应的字符就是他的 set.size();就是有多少个空。最后对字符排序。
#include <bits/stdc++.h>
using namespace std; char bin[][]; const int maxh = ;
const int maxw = ; int H,W;
int pic[maxh][maxw],color[maxh][maxw];
char line[maxw];
const int dr[] = {-,,,};
const int dc[] = {,,-,}; ///转成像素点图
void decode(char ch,int row,int col)
{
for(int i=; i<; i++)
{
pic[row][col+i] = bin[ch][i] - '';
}
} 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(row2>=&&row2<H&&col2>=&&col2<W&&pic[row2][col2]==pic[row][col]&&color[row2][col2]==)
{
dfs(row2,col2,c);
}
}
} const char* code = "WAKJSD"; vector<set<int> > neighbors; void check_neighbors(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&&pic[row2][col2]==&&color[row2][col2]!=)
{
neighbors[color[row][col]].insert(color[row2][col2]);
}
}
} char recognize(int c)
{
int cnt = neighbors[c].size();
return code[cnt];
} int main()
{
//freopen("in.txt","r",stdin);
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(color,,sizeof(color));
memset(pic,,sizeof(pic)); for(int i=;i<H;i++) {
scanf("%s",line);
for(int j=;j<W;j++) {
decode(line[j],i+,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(pic[i][j]==)
cc.push_back(cnt);
}
}
} neighbors.clear();
neighbors.resize(cnt+);
for(int i=;i<H;i++) {
for(int j=;j<W;j++) {
if(pic[i][j] == )
check_neighbors(i,j);
}
} vector<char> ans;
for(int i=;i<cc.size();i++)
ans.push_back(recognize(cc[i]));
sort(ans.begin(),ans.end()); printf("Case %d: ",++kase);
for(int i=;i<ans.size();i++)
printf("%c",ans[i]);
puts(""); } return ;
}