Question

2647. 把三角形染成红色

English Version

题目描述

现给定你一个整数 n 。考虑一个边长为 n 的等边三角形，被分成 n2 个单位等边三角形。这个三角形有 n 个 从 1 开始编号 的行，其中第 i 行有 2i - 1 个单位等边三角形。

第 i 行的三角形也是 从 1 开始编号 的，其坐标从 (i, 1) 到 (i, 2i - 1) 。下面的图像显示了一个边长为 4 的三角形及其三角形的索引。

如果两个三角形 共享一条边 ，则它们是 相邻 的。例如：

• 三角形 (1,1) 和 (2,2) 是相邻的。
• 三角形 (3,2) 和 (3,3) 是相邻的。
• 三角形 (2,2) 和 (3,3) 不相邻，因为它们没有共享任何边。

初始时，所有单位三角形都是 白色 的。你想选择 k 个三角形并将它们涂成 红色 。然后我们将运行以下算法：

1. 选择一个 至少有两个 红色相邻三角形的白色三角形。
   • 如果没有这样的三角形，请停止算法。
2. 将该三角形涂成 红色 。
3. 回到步骤 1。

选择最小的 k 并在运行此算法之前将 k 个三角形涂成红色，使得在算法停止后，所有单元三角形都被涂成红色。

返回一个二维列表，其中包含你要最初涂成红色的三角形的坐标。答案必须尽可能小。如果有多个有效的解决方案，请返回其中任意一个。

 

示例 1 ：

输入：n = 3
输出：[[1,1],[2,1],[2,3],[3,1],[3,5]]
解释：初始时，我们选择展示的5个三角形染成红色。然后，我们运行以下算法：
- 选择(2,2)，它有三个红色相邻的三角形，并将其染成红色。
- 选择(3,2)，它有两个红色相邻的三角形，并将其染成红色。
- 选择(3,4)，它有三个红色相邻的三角形，并将其染成红色。
- 选择(3,3)，它有三个红色相邻的三角形，并将其染成红色。 
可以证明，选择任何4个三角形并运行算法都无法将所有三角形都染成红色。

示例 2 ：

输入：n = 2
输出：[[1,1],[2,1],[2,3]]
解释：初始时，我们选择图中所示的 3 个三角形为红色。然后，我们运行以下算法： 
-选择有三个红色相邻的 (2,2) 三角形并将其染成红色。 
可以证明，选择任意 2 个三角形并运行该算法都不能使所有三角形变为红色。

 

提示：

• 1 <= n <= 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 colorRed(self, n: int) -> List[List[int]]:
    ans = [[1, 1]]
    k = 0
    for i in range(n, 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[][] colorRed(int n) {
    List<int[]> ans = new ArrayList<>();
    ans.add(new int[] {1, 1});
    for (int i = n, 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>> colorRed(int n) {
    vector<vector<int>> ans;
    ans.push_back({1, 1});
    for (int i = n, 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 colorRed(n int) (ans [][]int) {
  ans = append(ans, []int{1, 1})
  for i, k := n, 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
}

function colorRed(n: number): number[][] {
  const ans: number[][] = [[1, 1]];
  for (let i = n, k = 0; i > 1; --i, k = (k + 1) % 4) {
    if (k === 0) {
      for (let j = 1; j < i << 1; j += 2) {
        ans.push([i, j]);
      }
    } else if (k === 1) {
      ans.push([i, 2]);
    } else if (k === 2) {
      for (let j = 3; j < i << 1; j += 2) {
        ans.push([i, j]);
      }
    } else {
      ans.push([i, 1]);
    }
  }
  return ans;
}