原题: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 ;
}

最新文章

  1. org.apache.struts2.json.JSONWriter can not access a member of class
  2. 移动开发 android 入门开发 阶段视频
  3. 我存在,你深深的循环里--从反射看JSON死循环
  4. WinForm开发浏览器,WebBrowser获取页面内容,如何解决中文乱码
  5. 【mysql的编程专题⑥】视图
  6. Gson ------ 实例演习
  7. iOS中SQLite知识点总结1
  8. tomcat环境搭建
  9. iOS图片处理
  10. hdu 4710 Balls Rearrangement (数学思维)
  11. 1702: [Usaco2007 Mar]Gold Balanced Lineup 平衡的队列
  12. Java设计模式之策略设计模式
  13. Servlet之HTTP状态码
  14. iOS开发基础-图片切换(2)之懒加载
  15. CSS效果:3D卡片
  16. MTSC2019第五届中国移动互联网测试开发大会北京站震撼来袭!
  17. Codeforces 837E Vasya&#39;s Function - 数论
  18. Maven上传构建到私服
  19. File API
  20. office2010安装需MSXML版本6.10.1129.0详解解

热门文章

  1. asp.net mvc4 使用java异步提交form表单时出现[object object] has no method ajaxSubmit
  2. openwrt advanced configuration
  3. Oracle 10G强大的SQL优化工具:SQL Tuning Advisor
  4. power desinger 学习笔记&lt;六&gt;
  5. 深度探索va_start、va_arg、va_end
  6. Facade 模式
  7. 【POJ2406】【KMP】Power Strings
  8. 【POJ2761】【区间第k大】Feed the dogs(吐槽)
  9. CetnOS minimal 网络不可用
  10. Apache配置域名