题目描述建议直接洛谷或者看紫书 164页
题目描述
输入由几个测试用例组成,每个测试用例描述一个包含一个或多个的图像 象形文字选自图C.1所示的那些。图像以一系列水平扫描线的形式给出,这些水平扫描线由黑色像素(由1表示)和白色像素(由0表示)组成。在输入数据中,每个扫描线以十六进制表示法编码。 例如,序列将表示八个像素10011100(一个黑色像素,后面是两个白色像素,依此类推) 十六进制表示法为9c。 在十六进制中仅使用数字和小写字母a到f 编码。每个测试用例的第一行包含两个整数,H和W.H(0 <H≤200)是 图像中的扫描行数。 W(0 <W≤50)是每个中十六进制字符的数量 线。 接下来的H行包含图像的十六进制字符,从上到下工作。 输入图像符合以下规则: •图像仅包含图C.1中所示的象形文字。 •每个图像至少包含一个有效的象形文字。 •图像中的每个黑色像素都是有效象形文字的一部分。 •每个象形文字由一组连接的黑色像素组成,每个黑色像素至少有一个顶部,底部,左侧或右侧的其他黑色像素。 •象形文字没有触及,另一个象形文字中没有象形文字。 •对角线接触的两个黑色像素将始终具有共同的触摸黑色像素。 •象形文字可能会扭曲,但每个都有一个在拓扑上等同于其中一个的形状 图C.1中的符号。 (如果每个都可以转换,两个数字在拓扑上是等价的 通过伸展而不撕裂进入另一个。) 最后一个测试用例后跟一行包含两个零的行。
样例
建议看洛谷的讨论版
思路:
先观察这些图形,每一个图形中间的空洞数目是不同的,所以根据中间的白色洞来确定是哪一个图形,首先要把图形周围的所有白色区域标记一下,这里就需要把整个图形放大一圈,原因见图:
如果是这样图形靠近整个图的边缘区域,那么右上角的那一块白色区域不会被标记到,所以要多开一圈
注意!!!!!:
难点除了判断图形我认为还有进制的转换,16进制转换为2进制,在这里可以用数组来进行转换,一个一维数组表示16进制,一个二维数组来表示对应的二进制
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
char onesix[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
int st[20][4] = {{0,0,0,0}, {0,0,0,1}, {0,0,1,0}, {0,0,1,1},
{0,1,0,0}, {0,1,0,1}, {0,1,1,0}, {0,1,1,1},
{1,0,0,0}, {1,0,0,1}, {1,0,1,0}, {1,0,1,1},
{1,1,0,0}, {1,1,0,1}, {1,1,1,0}, {1,1,1,1}};
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int vis[N][N];
char w[N][N];
int n, m;
int check(int x, int y)
{
if(x >= 0 && x <= n + 1 && y >= 0 && y <= m + 1) return 1; ///为了完整标记多开一圈
return 0;
}
void dfs_findblacks(int x, int y)
{
for(int i = 0; i < 4; i++){
int tx = x + dx[i], ty = y + dy[i];
if(check(tx, ty) && !vis[tx][ty] && !w[tx][ty]){ ///没有被访问过并且没有越界的白点
vis[tx][ty] = 1;
dfs_findblacks(tx, ty);
}
}
}
int sum = 0;
void dfs_findans(int x, int y)
{
if(!w[x][y]) { ///找到了一个洞
sum++;
dfs_findblacks(x, y); ///标记这个洞内所有白点
return ;
}
for(int i = 0; i < 4; i++){
int tx = x + dx[i], ty = y + dy[i];
if(check(tx , ty) && !vis[tx][ty]){ ///因为每个图案不会相互接触,所以不会跑到另一个图去(中间一定有白点间隔)
vis[tx][ty] = 1;
dfs_findans(tx, ty);
}
}
}
int main()
{
int cases = 1;
while(scanf("%d%d",&n,&m)!=EOF&&n+m){
map<char, int> mp;
//scanf("%d%d", &n, &m);
//if(!n && !m) break;
memset(vis, 0, sizeof vis);
memset(w, 0, sizeof w);
for(int i = 1; i <= n; i++){
int p = 0;
char c;
for(int j = 1; j <= m; j++){
cin >> c;
for(int k = 0; k <= 15; k++){ ///16进制转2进制
if(onesix[k] == c){
for(int g = 0; g <= 3; g++){
w[i][++p] = st[k][g];
}
}
}
}
}
m *= 4; ///每一个16进制对应4位2进制,所以每行长度要乘4
vis[0][0] = 1;
dfs_findblacks(0 , 0); ///确定轮廓(把黑点以外的所有白点全部标记,洞内白点未标记)
///遇到黑点不进入递归,所以标记的都是轮廓外的白点
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(!vis[i][j] && w[i][j]){ ///找到没有被访问的黑点(即一个图案)
sum = 0;
dfs_findans(i, j);
if(sum == 0) mp['W']++;
else if(sum == 1) mp['A']++;
else if(sum == 2) mp['K']++;
else if(sum == 3) mp['J']++;
else if(sum == 4) mp['S']++;
else mp['D']++;
}
}
}
printf("Case %d: ", cases++);
for(auto i : mp){
while(i.second--){
printf("%c",i.first);
}
}
printf("\n");
}
return 0;
}