uva_1103 刘汝佳《算法竞赛入门经典》例6-13象形文字识别（连通图的综合应用）

连通图问题 较为综合性题目：#象形文字判断#

问题描述：

Figure C.1 shows six hieroglyphs and their names. In this problem, you will write a program to recognize these six characters.

题意：

    输入以16进制形式矩阵表示的0 1（0代表白色像素点，1代表黑色像素点）图像，判断图像中包含以上哪些象形文字。其中一幅图像可能包含多个象形文字，结果按照字典序进行输出。•图像仅包含图C.1中所示的象形文字。•每个图像至少包含一个有效的象形文字。•图像中的每个黑色像素都是有效象形文字的一部分。•每个象形文字由一组连接的黑色像素组成，每个黑色像素至少有一个顶部，底部，左侧或右侧的其他黑色像素。•象形文字没有触及，另一个象形文字中没有象形文字。•对角线接触的两个黑色像素将始终具有共同的触摸黑色像素。•象形文字可能会扭曲，但每个都有一个在拓扑上等同于其中一个的形状 图C.1中的符号。 （如果每个都可以转换，两个数字在拓扑上是等价的 通过伸展而不撕裂进入另一个。）

题目给出了对于象形文字的编码：

Ankh: A
Wedjat: J 
Djed: D 
Scarab: S 
Was: W 
Akhet: K

例：

核心问题：
1、如何通过像素(0,1)图像判断是哪种象形文字？

答：这是一个从抽象的图形问题转化为具体的数字/特征问题的过程，开始的时候自己没有思路，注意到了题目中说的拓扑等价，但还是没有具体的判断办法。
对此，入门经典书中所说的是数空洞的个数。图C中象形文字对应的空洞个数分别为：1，3，5，4，0，2。这样一来，就把一个抽象的图像问题转化成了连通图（白像素点）的个数判断问题。
对于此种以图像作为输入的问题，要通过找图像的特征属性来解决问题！

2、如何数白洞
自己第一个想法是：
* 找到一个未被标记的白像素点
* 判断该点是否上下左右延伸边界都是黑点（以此来判断该点是不是白洞内点）
* 若是，则将连通的白像素点全部标记，白洞个数加一。

但善于观察的读者可以发现，这个方法是不正确的，原因在于象形文字具有斜度所以有些点虽然满足前两个条件但其实并不是白洞内点。
例如这个槽内的点：

在发现后进行了改正：直接无差异地遍历白点，在DFS遍历过程中添加一个标志量，在遍历连通白点的过程中判断是否到达图像边界，如果能够到达边界则将标志量置为false说明这些点均为白洞外的无效点。
这样一来就成功解决了数白洞的问题。

代码：

    void dfs_w(int x,int y,bool &if_in)//将洞内的白点连通并标记{flag[x][y] = true;for(int i=0;i<8;i++){int nx=x+mov[i][0];int ny=y+mov[i][1];if(!legal(nx,ny))//能够到达边界说明不是内点{if_in = false;}else if(!binary[nx][ny]&&!flag[nx][ny]){dfs_w(nx,ny,if_in);}}}

3、一个图像中包含多个文字，如何区分出来？
此问题以前的分析都是建立在图像中只有一个文字的前提下，不幸的是题目中说一幅图像会包含>=1个象形文字。
那么如何判断图像中有几个文字，一个空洞属于哪个文字呢？
第一个问题：同样是数连通图的方法，同时对每个独立的连通图进行编号。这样也就顺带解决了第二个问题。
对于一个白洞，只要沿任意方向找个一个黑像素点，判断此黑像素点属于哪个文字，就在此文字的白洞数量上加1。

代码：

int cnt=0;//文字个数for(int i=0;i<h;i++)for(int j=0;j<4*w;j++){if(binary[i][j]&&!flag_b[i][j]){dfs_b(i,j,++cnt);}}

void dfs_b(int x,int y,int cnt)//将图像内的文字编号 cnt
{flag_b[x][y] = cnt;for(int i=0;i<8;i++){int nx=x+mov[i][0];int ny=y+mov[i][1];if(legal(nx,ny)&&binary[nx][ny]&&!flag_b[nx][ny]){dfs_b(nx,ny,cnt);}}
}

for(int i=0;i<h;i++)//遍历白洞同时给对应我文字添加白洞个数for(int j=0;j<4*w;j++){if(!binary[i][j]&&!flag[i][j]){bool if_in=true;dfs_w(i,j,if_in);if(if_in){int tmp_j=j;while(!binary[i][++tmp_j]){}//注意这里的要写++tmp_j，否则取得的位置是黑像素点的下个位置。num_hole[flag_b[i][tmp_j]]++;//文字白洞个数+1}}}

全部代码：

#include<bits/stdc++.h>
using namespace std;int h,w;
char image[210][55];
int binary[210][210];
bool flag[210][210];
int flag_b[210][210];
int num_hole[1000];
int mov[8][2]={-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};
char code[6]={'W','A','K','J','S','D'};void get_image()
{for(int i=0;i<h;i++)for(int j=0;j<w;j++){cin>>image[i][j];}
}void get_binary()//与上面其实可以合并
{for(int i=0;i<h;i++){for(int j=0;j<w;j++){char c = image[i][j];int tmp;if(isalpha(c))tmp = c-'a'+10;elsetmp = c - '0';binary[i][j*4] = tmp/8;tmp%=8;//将16进制转化为2进制的一个小trickbinary[i][j*4+1] = tmp/4;tmp%=4;binary[i][j*4+2] = tmp/2;binary[i][j*4+3] = tmp%2;}}}bool legal(int x,int y)
{if(x>=0&&x<h&&y>=0&&y<w*4)return true;elsereturn false;
}void dfs_b(int x,int y,int cnt)//将图像内的文字编号
{flag_b[x][y] = cnt;for(int i=0;i<8;i++){int nx=x+mov[i][0];int ny=y+mov[i][1];if(legal(nx,ny)&&binary[nx][ny]&&!flag_b[nx][ny]){dfs_b(nx,ny,cnt);}}
}void dfs_w(int x,int y,bool &if_in)//将洞内的白点连通并标记
{flag[x][y] = true;for(int i=0;i<8;i++){int nx=x+mov[i][0];int ny=y+mov[i][1];if(!legal(nx,ny))//能够到达边界说明不是内点{if_in = false;}else if(!binary[nx][ny]&&!flag[nx][ny]){dfs_w(nx,ny,if_in);}}
}int main()
{int T=0;while(cin>>h>>w&&h){memset(flag,false,sizeof(flag));memset(flag_b,0,sizeof(flag_b));memset(num_hole,0,sizeof(num_hole));get_image();get_binary();int cnt=0;for(int i=0;i<h;i++)for(int j=0;j<4*w;j++){if(binary[i][j]&&!flag_b[i][j]){dfs_b(i,j,++cnt);}}for(int i=0;i<h;i++)for(int j=0;j<4*w;j++){if(!binary[i][j]&&!flag[i][j]){bool if_in=true;dfs_w(i,j,if_in);if(if_in){//cout<<"yes"<<endl;int tmp_j=j;while(!binary[i][++tmp_j]){}//cout<<i<<" "<<tmp_j<<endl;num_hole[flag_b[i][tmp_j]]++;}}}printf("Case %d: ",++T);vector<char>v;for(int i=1;i<=cnt;i++){//cout<<num_hole[i]<<endl;v.push_back(code[num_hole[i]]);}sort(v.begin(),v.end());for(int i=0;i<v.size();i++)printf("%c",v[i]);printf("\n");}return 0;
}