Ancient Message (古埃及象形文字识别 Uva 1103)
2024-08-25 18:47:37
原题:https://uva.onlinejudge.org/external/11/1103.pdf
给一幅图(16进制), 判断图中有哪些象形文字。
只识别
这6个就可以
示例:
将16进制数据
转换为
二进制数据
然后输出象形文字的名字
原理: 其实很简单,因为这六个象形文字比较特殊,每个文字包含的空心部分个数不一样。
比如Ankh有一个空心部分,Wedjat有3个空心部分。所以只要先用dfs找到象形文字,然后数一数
每个有几个空心部分就可以了。
#include <cstdio>
#include <cstring>
#include <utility>
#include <set>
#include <algorithm>
#include <vector>
using namespace std; const int MAXN = + ;
bool pic[MAXN][MAXN], record[MAXN][MAXN];
const char *name = "WAKJSD";
int f[MAXN][MAXN], dx[] = {, -, , }, dy[] = {, , -, };
int cnt, H, W, T;
vector<pair<int, int> > startp; void init_read() {
char s[]; cnt = ; H += ; int NW = * W + ;
memset(pic, , sizeof(pic));
memset(f, , sizeof(f));
memset(record, , sizeof(record));
startp.clear();
for (int i = ; i < NW; i++) pic[][i] = pic[H - ][i] = ;
for (int i = ; i < H; i++) pic[i][] = pic[i][NW - ] = ;
for (int i = ; i < H - ; i++) {
scanf("%s", s);
for (int j = ; j < W; j++) {
int num = s[j] > '' ? s[j] - 'a' + : s[j] - '';
for (int k = ; k < ; k++)
if (num >= ( << ( - k))) { pic[i][j * + k + ] = ; num -= ( << ( - k));}
}
}
W = NW;
} void colorization(int x, int y, bool c) {
f[x][y] = cnt;
for (int i = ; i < ; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= && ny >= && nx < H && ny < W && pic[nx][ny] == c && !f[nx][ny])
colorization(nx, ny, c);
}
}
void floodfill() {
for (int i = ; i < H; i++)
for (int j = ; j < W; j++)
if (!f[i][j]) {
cnt++; colorization(i, j, pic[i][j]);
if (pic[i][j]) startp.push_back(make_pair(i, j));
}
} void get_signiture(set<int> &signature, int x, int y) {
record[x][y] = ;
for (int i = ; i < ; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= && ny >= && nx < H && ny < W) {
if (f[nx][ny] != f[x][y]) signature.insert(f[nx][ny]);
else if(f[nx][ny] == f[x][y] && !record[nx][ny])
get_signiture(signature, nx, ny);
}
}
}
void recognize() {
vector<char> ans;
int n = startp.size();
for (int i = ; i < n; i++) {
int x = startp[i].first, y = startp[i].second;
set<int> signature;
get_signiture(signature, x, y);
ans.push_back(name[signature.size() - ]);
}
sort(ans.begin(), ans.end());
printf("Case %d: ", ++T);
for (int i = ; i < n; i++)
printf("%c", ans[i]);
printf("\n");
} int main() {
while (scanf("%d%d", &H, &W) == && H) {
init_read();
floodfill();
recognize();
}
return ;
}
最新文章
- org.apache.struts2.json.JSONWriter can not access a member of class
- 移动开发 android 入门开发 阶段视频
- 我存在,你深深的循环里--从反射看JSON死循环
- WinForm开发浏览器,WebBrowser获取页面内容,如何解决中文乱码
- 【mysql的编程专题⑥】视图
- Gson ------ 实例演习
- iOS中SQLite知识点总结1
- tomcat环境搭建
- iOS图片处理
- hdu 4710 Balls Rearrangement (数学思维)
- 1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列
- Java设计模式之策略设计模式
- Servlet之HTTP状态码
- iOS开发基础-图片切换(2)之懒加载
- CSS效果:3D卡片
- MTSC2019第五届中国移动互联网测试开发大会北京站震撼来袭!
- Codeforces 837E Vasya&#39;s Function - 数论
- Maven上传构建到私服
- File API
- office2010安装需MSXML版本6.10.1129.0详解解
热门文章
- asp.net mvc4 使用java异步提交form表单时出现[object object] has no method ajaxSubmit
- openwrt advanced configuration
- Oracle 10G强大的SQL优化工具:SQL Tuning Advisor
- power desinger 学习笔记<;六>;
- 深度探索va_start、va_arg、va_end
- Facade 模式
- 【POJ2406】【KMP】Power Strings
- 【POJ2761】【区间第k大】Feed the dogs(吐槽)
- CetnOS minimal 网络不可用
- Apache配置域名