-
Notifications
You must be signed in to change notification settings - Fork 1
/
uva297.cpp
61 lines (53 loc) · 1.39 KB
/
uva297.cpp
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
#include <iostream>
using namespace std;
struct Node {
char val;
Node* child[4];
Node(char val) : val(val) {}
};
Node *root1, *root2;
int sum;
char readchar() {
char ch;
while(ch = getchar(), !isalpha(ch));
return ch;
}
// assert u != NULL
void build(Node* u) {
if(!u || u->val != 'p') return;
for(int i = 0; i < 4; i++) {
u->child[i] = new Node(readchar());
build(u->child[i]);
}
}
void make_empty_child(Node* u) {
for(int i = 0; i < 4; i++) {
u->child[i] = new Node('e');
}
}
void solve(Node *u, Node *v, int val) {
// 其中一个是黑,则全黑,sum += val, return
// 其中一个p,另一个白,则为白的分配4个白色子节点,开始子节点的匹配
// 2个白,直接return
// 2个p,开始子节点的匹配
if(u->val == 'f' || v->val == 'f') {sum += val; return;}
if(u->val == 'e' && v->val == 'e') return;
if(u->val == 'e') make_empty_child(u);
if(v->val == 'e') make_empty_child(v);
for(int i = 0; i < 4; i++) {
solve(u->child[i], v->child[i], val / 4);
}
}
int main(void) {
int T; scanf("%d", &T);
while(T--) {
root1 = new Node(readchar());
build(root1);
root2 = new Node(readchar());
build(root2);
sum = 0;
solve(root1, root2, 1024);
printf("There are %d black pixels.\n", sum);
}
return 0;
}