沙地治理

运行时间: 82 ms

内存: 59.2 MB

class Solution:
    def sandyLandManagement(self, size: int) -> List[List[int]]:



        # public solution ... 
        """
        贪心法：

        首先，三角形的三个角都必须要种树，因为这三个位置只与另外一个三角形相邻。
        
        接下来，从贪心的角度除法，
        如果某个三角形已经与另一个绿洲三角形相邻，那么不到万不得已就不应该在这个三角形中种树，
        因为这样一来就浪费掉了这两个三角形相邻的那条边。方便起见，从底边开始向上考虑。

        首先，底边应该每隔一个空位种树，也就是在底边的所有正三角形种树。
        接下来，底边的所有倒三角形都会在相邻的两个正三角形的影响下变为绿洲。

        接下来对于倒数第二行，所有正三角形的底边与最后一行倒三角形的顶边相邻，因此原则上不应该在这些位置上种树。
        对于倒数第二行的倒三角，第一个倒三角上应该种树。第一个倒三角种上树之后，第一个正三角以及第二个正三角都会变为绿洲，
        因此第二个倒三角不应该种树，而是应该在第三个倒三角种树，
        通过第三个倒三角将第三个正三角变为绿洲，
        然后通过第二个和第三个正三角将第二个倒三角变为绿洲。

        更一般的，在这里可以使用一个标记near_flag表示对于当前处理的倒三角是否已经被相邻的正三角影响到一条边。
        若near_flag为true，那么就应该标记下一个倒三角，否则就标记当前倒三角，并将near_flag置为true。

        除此之外，有一种特殊情况就是来到当前行的末尾时，
        如果触发了near_flag，那么就应该标记当前倒三角正上方的正三角从而避免浪费，
        因此在具体处理是，应该是从倒数第二行开始，沿之字型从下往上进行填充。
        """

        if size == 1:
            return [[1, 1]]
        
        res = [[1, 1]]
        
        for j in range(1, 2*size, 2):
            res.append([size, j])
        
        if size == 2:
            return res
        
        i = size - 1
        while i > 1:
            res.append([i, 2])
            
            if i - 1 == 1:
                return res
            
            for j in range(3, 2*(i - 1), 2):
                res.append([i - 1, j])
            
            if i - 2 == 1:
                return res
            
            res.append([i - 2, 1])
            
            if i - 3 == 1:
                return res
            
            for j in range(1, 2*(i - 3), 2):
                res.append([i - 3, j])
            
            i -= 4
        
        return res