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
|
// 427. Construct Quad Tree
#include <bits/stdc++.h>
using namespace std;
#define vvd(data) vector<vector<data>>
/*
* wtf this is right pants for a medium
*/
class Node {
public:
bool val;
bool isLeaf;
Node *topLeft;
Node *topRight;
Node *bottomLeft;
Node *bottomRight;
Node() {
val = false;
isLeaf = false;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
Node(bool _val, bool _isLeaf, Node *_topLeft, Node *_topRight,
Node *_bottomLeft, Node *_bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
class Solution {
public:
Node *construct(vvd & grid) {
grid_v = move(grid);
leafNodes_a[0] = new Node(false, true, nullptr, nullptr, nullptr, nullptr);
leafNodes_a[1] = new Node(true, true, nullptr, nullptr, nullptr, nullptr);
return construct(0, 0, grid_v.size());
}
private:
vvd grid_v;
array<Node *, 2> leafNodes_a;
Node *construct(int r, int c, int s) {
if (s == 1)
return leafNodes_a[grid_v[r][c]];
s /= 2;
Node *tl = construct(r, c, s);
Node *tr = construct(r, c + s, s);
Node *bl = construct(r + s, c, s);
Node *br = construct(r + s, c + s, s);
if (tl == tr && tl == bl && tl == br)
return tl;
return new Node(false, false, tl, tr, bl, br);
}
};
int main() {
Solution obj;
vvd grid = {{0, 1}, {1, 0}};
cout << obj.construct(grid); // expect: [[0,1],[1,0],[1,1],[1,1],[1,0]]
}
|