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

本文主要是介绍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;
}

这篇关于uva_1103 刘汝佳《算法竞赛入门经典》例6-13象形文字识别(连通图的综合应用)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/405217

相关文章

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》:本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

Java MQTT实战应用

《JavaMQTT实战应用》本文详解MQTT协议,涵盖其发布/订阅机制、低功耗高效特性、三种服务质量等级(QoS0/1/2),以及客户端、代理、主题的核心概念,最后提供Linux部署教程、Sprin... 目录一、MQTT协议二、MQTT优点三、三种服务质量等级四、客户端、代理、主题1. 客户端(Clien

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么?能干嘛?核心作用:二、索引的 4 种主要类型(附通俗例子)1. BTree 索引(

Redis 配置文件使用建议redis.conf 从入门到实战

《Redis配置文件使用建议redis.conf从入门到实战》Redis配置方式包括配置文件、命令行参数、运行时CONFIG命令,支持动态修改参数及持久化,常用项涉及端口、绑定、内存策略等,版本8... 目录一、Redis.conf 是什么?二、命令行方式传参(适用于测试)三、运行时动态修改配置(不重启服务

MySQL DQL从入门到精通

《MySQLDQL从入门到精通》通过DQL,我们可以从数据库中检索出所需的数据,进行各种复杂的数据分析和处理,本文将深入探讨MySQLDQL的各个方面,帮助你全面掌握这一重要技能,感兴趣的朋友跟随小... 目录一、DQL 基础:SELECT 语句入门二、数据过滤:WHERE 子句的使用三、结果排序:ORDE