UVA 1103 Ancient Messages

发表于 | 分类于 ，

题意：给定一个黑白图片的16进制表示，识别出图片中包含的象形文字。

首先需要把十六进制表示转化为二进制表示。因为每个象形文字的黑色像素是连通的，所以黑色像素的连通分量的数目即为象形文字的数目。各象形文字可以用其包含的白色区域的数目来区别。想到的做法是，dfs填充白色像素区域，并返回区域的边界：0 表示没有边界（边界都是白色像素），1,2,3… 表示边界是对应的黑色连通分量，-1 表示边界是整个图像的边界。若边界是黑色像素，则对应的黑色连通分量包含的白色区域数+1。这样，即可区分出不同的象形文字。

一个想错的地方是，认为返回的区域边界不会为0。想象这样一种情况，一个白色像素其周围的三个白色像素都已经遍历到，则返回0。而这种情况是有可能的。

紫书中的做法是增加了白色边界，方便处理；从黑色区域找与其相连的白色区域。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>

using namespace std;

const int MAX_H = 200 + 10;
const int MAX_W = 50 * 4 + 10;

int H, W;
char image[MAX_H][MAX_W];
int cmp[MAX_H][MAX_W];

int to_int(char ch) {
  if ('0' <= ch && ch <= '9') return ch - '0';
  return 10 + ch - 'a';
}

int dX[] = {0, -1, 0, 1}, dY[] = {-1, 0, 1, 0};
void dfs(int x, int y, int c) {
  cmp[x][y] = c;
  for (int i = 0; i < 4; i++) {
    int nx = x + dX[i], ny = y + dY[i];
    if (0 <= nx && nx < H && 0 <= ny && ny < W &&
        image[nx][ny] == '1' && cmp[nx][ny] == 0) {
      dfs(nx, ny, c);
    }
  }
}

int fill(int x, int y, int c) {
  cmp[x][y] = c;
  int b = 0;
  for (int i = 0; i < 4; i++) {
    int nx = x + dX[i], ny = y + dY[i];
    if (nx < 0 || nx >= H || ny < 0 || ny >= W) {
      b = -1;
      continue;
    }
    if (image[nx][ny] == '1') {
      b = b == -1 ? b : cmp[nx][ny];
      continue;
    }
    if (cmp[nx][ny] == 0) {
      int r = fill(nx, ny, c);
      // order 0 < 1,2,3... < -1
      b = r == -1 ? r : (b == -1 ? b : max(b, r));
    }
  }
  return b; // b maybe 0
}

int main() {
  int T = 1;
  while (scanf("%d %d", &H, &W) && H) {
    memset(image, 0, sizeof(image));
    for (int i = 0; i < H; i++)
      scanf("%s", image[i]);

    for (int i = 0; i < H; i++) {
      for (int j = W - 1; j >= 0; j--) {
        for (int k = 0; k < 4; k++) {
          int t = to_int(image[i][j]);
          image[i][(j + 1) * 4 - 1 - k] = ((t >> k) & 1) ? '1' : '0';
        }
      }
    }
    W = W * 4;

    memset(cmp, 0, sizeof(cmp));
    int num = 0;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (image[i][j] == '1' && cmp[i][j] == 0) {
          dfs(i, j, ++num);
        }
      }
    }

    vector<int> area(num + 1, 0);
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (image[i][j] == '0' && cmp[i][j] == 0) {
          int b = fill(i, j, ++num);
          if (b != -1) area[b]++;
        }
      }
    }

    vector<char> ans;
    char mp[] = {'W', 'A', 'K', 'J', 'S', 'D'};
    for (int i = 1; i < area.size(); i++) {
      ans.push_back(mp[area[i]]);
    }
    sort(ans.begin(), ans.end());
    printf("Case %d: ", T++);
    for (int i = 0; i < ans.size(); i++) {
      printf("%c", ans[i]);
    }
    printf("\n");
  }
  return 0;
}