UVA 297 Quadtrees

发表于 | 分类于 ，

题意：给定两个四分树的先序遍历序列，四分树的每个结点与图像的某个区域对应，求两个图像合并后黑色像素的数目。

想到的做法是同时遍历两个四分树，在遍历的过程中遇到p结点则向下；如果两个结点都不是p结点且其中一个为f结点，则加上对应区域的像素数目。

紫书中的解法是考虑四分树对应的图像。一个学到的地方是（正方形）区域的表示：区域的左上角坐标(x,y)以及区域的宽度w。这样，在表示四分区域时非常方便。

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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1 << 11;

char s1[MAX_N], s2[MAX_N];

void scan(int& i, int d1, int& j, int d2, int& ans) {
  bool p1 = s1[i] == 'p', p2 = s2[j] == 'p';
  if (p1 || p2) {
    for (int k = 0; k < 4; k++) {
      scan(p1 ? ++i : i, p1 ? d1 - 1 : d1,
           p2 ? ++j : j, p2 ? d2 - 1 : d2,
           ans);
    }
  } else {
    if (s1[i] == 'f' || s2[j] == 'f') {
      ans += (1 << min(d1, d2)) * (1 << min(d1, d2));
    }
  }
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%s %s", s1, s2);
    int ans = 0;
    int i = 0, j = 0;
    scan(i, 5, j, 5, ans);
    printf("There are %d black pixels.\n", ans);
  }
  return 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
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1 << 11;
const int W = 32;

char s1[MAX_N], s2[MAX_N];
bool pic[W][W];

void draw(char* s, int& p, int x, int y, int w) {
  if (s[p] == 'p') {
    draw(s, ++p, x, y + w / 2, w / 2);
    draw(s, ++p, x, y, w / 2);
    draw(s, ++p, x + w / 2, y, w / 2);
    draw(s, ++p, x + w / 2, y + w / 2, w / 2);
  } else if (s[p] == 'f') {
    for (int i = 0; i < w; i++) {
      for (int j = 0; j < w; j++) {
        pic[x + i][y + j] = true;
      }
    }
  }
}

int main() {
  int T; scanf("%d", &T);
  while (T--) {
    scanf("%s %s", s1, s2);
    memset(pic, 0, sizeof(pic));
    int p = 0;
    draw(s1, p, 0, 0, W);
    p = 0;
    draw(s2, p, 0, 0, W);
    int ans = 0;
    for (int i = 0; i < W; i++) {
      for (int j = 0; j < W; j++) {
        if (pic[i][j]) ans++;
      }
    }
    printf("There are %d black pixels.\n", ans);
  }
  return 0;
}