时间戳

首页 > 解决方案 > 如何递归和迭代地分割盒子里面的盒子？

python - 如何递归和迭代地分割盒子里面的盒子？

问题描述

class Point:
    def __init__(self, x, y):
        self.x=x
        self.y=y
class Rect:
    def __init__(self, up, dw):
        self.up=up
        self.dw=dw
        self.next=[]
    def next_empty(self):
        return len(self.next)<=0



def inside(p1, p2, p3):
    return p3.x>=p1.x and p3.y<=p1.y and p3.x<=p2.x and p3.y>=p3.y

def create_box(root, parts):
    width=root.dw.x-root.up.x
    height=root.up.y-root.dw.y
    divx=width/parts
    divy=height/parts

    x=y=0
    for _y in range(parts):
        for _x in range(parts):
            rect=Rect(up=Point(x, y+divy), dw=Point(x+divx, y))
            root.next.append(rect)
            x+=divx
        x=0
        y+=divy
    return True

def create_tree(root, parts, n=2):
    pass
    
    

up=Point(0, 180)
dw=Point(360, 0)
root=Rect(up, dw)

#create_tree(root, 20)

上面的代码有两个类Point和Rect。Point 表示图形上的一个点，Rect 表示一个矩形，'Rect.up' 属性是左上角的点，而'Rect.dw' 是右下角的点。

create_box 函数将给定的 rect 对象划分为parts*parts 矩形并将其保存在“Rect.next”数组中。所以第一个矩形是 up=(18, 0) dw=(18,0)，第二个是 up=(18, 18) dw=(36, 0)。我有一个 create_tree 函数，它应该创建 n 个节点的树，但我在这里遇到了一些问题。例如：首先创建树将根分为 x 部分，这些 x 部分将再次分为 x 部分，类似地，此过程将继续直到达到 n 个节点。我希望 create_tree 函数能够以以下行为工作：-

def create_tree(root, parts, n=2):
    root_arr=[root]
    # when n=1
    if n==1:
        for r in root_arr:
            create_box(r, parts)

    #when n=2
    if n==2:
        for r in root_arr:
            create_box(r, parts)
        for r in root_arr:
            for j in r.next:
                create_box(j, parts)
    # when n=3
    if n==3:
        for r in root_arr:
            create_box(r, parts)
        for r in root_arr:
            for j in r.next:
                create_box(j, parts)
        for r in root_arr:
            for j in r.next:
                for q in j.next:
                    create_box(q, parts)
# N can be any number

我在添加这种循环时遇到了麻烦。应该如何同时使用递归和迭代来解决它？

标签： pythonpython-3.xalgorithmpython-2.x

解决方案

使用 DFS 方法，您可以编写一个递归函数来包装盒子创建任务：

def create_boxes_recursively(root, parts, levels):
    root_arr = [root]
    create_box(root, parts)
    if levels==1:
        return
    if not root.next:
        return
    for j in root.next:
        create_boxes_recursively(j, parts, levels-1)

至于迭代，您可以使用 BFS 方法，该方法跟踪下一级的所有节点：

def create_boxes_iteratively(root, parts, levels):
    next_nodes = [root]
    curr_level = 0
    while next_nodes and curr_level<levels:
        temp_array = []
        for node in next_nodes:
            create_box(node, parts)
            temp_array += node.next
        curr_level += 1
        next_nodes = temp_array

推荐阅读