Question

LCP 70. 沙地治理

题目描述

在力扣城的沙漠分会场展示了一种沙柳树，这种沙柳树能够将沙地转化为坚实的绿地。 展示的区域为正三角形，这片区域可以拆分为若干个子区域，每个子区域都是边长为 1  的小三角形，其中第  i 行有  2i - 1  个小三角形。

初始情况下，区域中的所有位置都为沙地，你需要指定一些子区域种植沙柳树成为绿地，以达到转化整片区域为绿地的最终目的，规则如下：

• 若两个子区域共用一条边，则视为相邻； > 如下图所示，(1,1)和(2,2)相邻，(3,2)和(3,3)相邻；(2,2)和(3,3)不相邻，因为它们没有共用边。
• 若至少有两片绿地与同一片沙地相邻，则这片沙地也会转化为绿地
• 转化为绿地的区域会影响其相邻的沙地
  

现要将一片边长为 size  的沙地全部转化为绿地，请找到任意一种初始指定 最少 数量子区域种植沙柳的方案，并返回所有初始种植沙柳树的绿地坐标。

示例 1：

输入：size = 3 输出：[[1,1],[2,1],[2,3],[3,1],[3,5]] 解释：如下图所示，一种方案为： 指定所示的 5 个子区域为绿地。 相邻至少两片绿地的 (2,2)，(3,2) 和 (3,4) 演变为绿地。 相邻两片绿地的 (3,3) 演变为绿地。

示例 2：

输入：size = 2 输出：[[1,1],[2,1],[2,3]] 解释：如下图所示： 指定所示的 3 个子区域为绿地。 相邻三片绿地的 (2,2) 演变为绿地。

提示：

• 1 <= size <= 1000

解法

方法一：找规律

我们画图观察，可以发现，第一行只有一个三角形，一定要涂色，而从最后一行开始，到第二行结束，每四行的涂色方案是一样的：

1. 最后一行涂色坐标为 $(n, 1)$, $(n, 3)$, …, $(n, 2n - 1)$。
2. 第 $n - 1$ 行涂色坐标为 $(n - 1, 2)$。
3. 第 $n - 2$ 行涂色坐标为 $(n - 2, 3)$, $(n - 2, 5)$, …, $(n - 2, 2n - 5)$。
4. 第 $n - 3$ 行涂色坐标为 $(n - 3, 1)$。

因此，我们可以按照上述规律，先给第一行涂色，然后从最后一行开始，每四行涂色一次，直到第二行结束。

时间复杂度 $(n^2)$，其中 $n$ 为题目给定的参数。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

class Solution:
  def sandyLandManagement(self, size: int) -> List[List[int]]:
    ans = [[1, 1]]
    k = 0
    for i in range(size, 1, -1):
      if k == 0:
        for j in range(1, i << 1, 2):
          ans.append([i, j])
      elif k == 1:
        ans.append([i, 2])
      elif k == 2:
        for j in range(3, i << 1, 2):
          ans.append([i, j])
      else:
        ans.append([i, 1])
      k = (k + 1) % 4
    return ans

class Solution {
  public int[][] sandyLandManagement(int size) {
    List<int[]> ans = new ArrayList<>();
    ans.add(new int[] {1, 1});
    for (int i = size, k = 0; i > 1; --i, k = (k + 1) % 4) {
      if (k == 0) {
        for (int j = 1; j < i << 1; j += 2) {
          ans.add(new int[] {i, j});
        }
      } else if (k == 1) {
        ans.add(new int[] {i, 2});
      } else if (k == 2) {
        for (int j = 3; j < i << 1; j += 2) {
          ans.add(new int[] {i, j});
        }
      } else {
        ans.add(new int[] {i, 1});
      }
    }
    return ans.toArray(new int[0][]);
  }
}

class Solution {
public:
  vector<vector<int>> sandyLandManagement(int size) {
    vector<vector<int>> ans;
    ans.push_back({1, 1});
    for (int i = size, k = 0; i > 1; --i, k = (k + 1) % 4) {
      if (k == 0) {
        for (int j = 1; j < i << 1; j += 2) {
          ans.push_back({i, j});
        }
      } else if (k == 1) {
        ans.push_back({i, 2});
      } else if (k == 2) {
        for (int j = 3; j < i << 1; j += 2) {
          ans.push_back({i, j});
        }
      } else {
        ans.push_back({i, 1});
      }
    }
    return ans;
  }
};

func sandyLandManagement(size int) (ans [][]int) {
  ans = append(ans, []int{1, 1})
  for i, k := size, 0; i > 1; i, k = i-1, (k+1)%4 {
    if k == 0 {
      for j := 1; j < i<<1; j += 2 {
        ans = append(ans, []int{i, j})
      }
    } else if k == 1 {
      ans = append(ans, []int{i, 2})
    } else if k == 2 {
      for j := 3; j < i<<1; j += 2 {
        ans = append(ans, []int{i, j})
      }
    } else {
      ans = append(ans, []int{i, 1})
    }
  }
  return
}