-
Notifications
You must be signed in to change notification settings - Fork 0
/
4.29.py
executable file
·31 lines (28 loc) · 1.21 KB
/
4.29.py
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
from typing import List
class Node:
def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def dfs(r0: int, c0: int, r1: int, c1: int) -> 'Node':
if all(grid[i][j] == grid[r0][c0] for i in range(r0, r1) for j in range(c0, c1)):
return Node(grid[r0][c0] == 1, True)
return Node(
True,
False,
dfs(r0, c0, (r0 + r1) // 2, (c0 + c1) // 2),
dfs(r0, (c0 + c1) // 2, (r0 + r1) // 2, c1),
dfs((r0 + r1) // 2, c0, r1, (c0 + c1) // 2),
dfs((r0 + r1) // 2, (c0 + c1) // 2, r1, c1),
)
return dfs(0, 0, len(grid), len(grid))
if __name__ =='__main__':
s = Solution()
a = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
r = s.construct(a)
print(r.bottomRight.val)