Uva 1103 古代象形文字

象形文字"/>

Uva 1103 古代象形文字

题目链接：

紫书P163.

1、根据16进制图转成2进制图。

每个点dfs一下，马上就把最外围的连通分量编号求出来了为1，这个不是文字里面的空白。

2、求每个文字，四周的空白有多少。——用一个set容器，当你查看这个像素为1 的点，发现四周的点的连通分量编号不同并且不是 1 ，就可以插入到 set 中，set 防止重复。然后这种像素点为 1 对应的字符就是他的 set.size();就是有多少个空。最后对字符排序。

#include <bits/stdc++.h>
using namespace std;char bin[256][5];const int maxh = 210;
const int maxw = 210;int H,W;
int pic[maxh][maxw],color[maxh][maxw];
char line[maxw];
const int dr[] = {-1,1,0,0};
const int dc[] = {0,0,-1,1};///转成像素点图
void decode(char ch,int row,int col)
{for(int i=0; i<4; i++){pic[row][col+i] = bin[ch][i] - '0';}
}void dfs(int row,int col,int c)
{color[row][col] = c;for(int i=0; i<4; i++){int row2 = row + dr[i];int col2 = col + dc[i];if(row2>=0&&row2<H&&col2>=0&&col2<W&&pic[row2][col2]==pic[row][col]&&color[row2][col2]==0){dfs(row2,col2,c);}}
}const char* code = "WAKJSD";vector<set<int> > neighbors;void check_neighbors(int row,int col)
{for(int i=0; i<4; i++){int row2 = row + dr[i];int col2 = col + dc[i];if(row2>=0&&row2<H&&col2>=0&&col2<W&&pic[row2][col2]==0&&color[row2][col2]!=1){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['0'], "0000");strcpy(bin['1'], "0001");strcpy(bin['2'], "0010");strcpy(bin['3'], "0011");strcpy(bin['4'], "0100");strcpy(bin['5'], "0101");strcpy(bin['6'], "0110");strcpy(bin['7'], "0111");strcpy(bin['8'], "1000");strcpy(bin['9'], "1001");strcpy(bin['a'], "1010");strcpy(bin['b'], "1011");strcpy(bin['c'], "1100");strcpy(bin['d'], "1101");strcpy(bin['e'], "1110");strcpy(bin['f'], "1111");int kase = 0;while(scanf("%d%d",&H,&W),H) {memset(color,0,sizeof(color));memset(pic,0,sizeof(pic));for(int i=0;i<H;i++) {scanf("%s",line);for(int j=0;j<W;j++) {decode(line[j],i+1,j*4+1);}}H+=2;W = W*4+2;int cnt = 0;vector<int> cc;memset(color,0,sizeof(color));for(int i=0;i<H;i++) {for(int j=0;j<W;j++) {if(!color[i][j]) {dfs(i,j,++cnt);if(pic[i][j]==1)cc.push_back(cnt);}}}neighbors.clear();neighbors.resize(cnt+1);for(int i=0;i<H;i++) {for(int j=0;j<W;j++) {if(pic[i][j] == 1)check_neighbors(i,j);}}vector<char> ans;for(int i=0;i<cc.size();i++)ans.push_back(recognize(cc[i]));sort(ans.begin(),ans.end());printf("Case %d: ",++kase);for(int i=0;i<ans.size();i++)printf("%c",ans[i]);puts("");}return 0;
}

转载于:.html