题意分析

问题描述

• 输入：给定一个由 n 行组成的三角形字母矩阵，每行有 i 个字母（i 从 1 到 n）。
• 输出：找出所有能构成等边三角形的字母（即存在至少三个相同字母，其位置构成等边三角形）。
• 约束：
  • 每个字母最多出现 3 次（防止过多解）。
  • 如果无解，输出 "LOOOOOOOOSER!"。
  • 结果按字母序排列。

示例分析

输入 1：

4
abccddadca

输出 1：

ac

• 解释：
  • a 出现在位置 (0,0), (3,0), (3,3)，可以构成等边三角形。
  • c 出现在位置 (1,1), (1,2), (2,2)，也可以构成等边三角形。

解题思路

1. 坐标映射

   • 将输入的字母按三角形坐标存储，例如第 i 行第 j 列的坐标计算方式：
     • x坐标：j - i / 2.0（水平偏移）
     • y坐标：-i * sqrt(3) / 2（垂直偏移）
   • 这样能保证等边三角形的几何性质。

2. 字母分组

   • 使用 unordered_map<char, vector<Point>> 存储每个字母的所有位置。

3. 等边三角形判定

   • 对于每个字母，检查是否存在三个点满足：
     • 两两之间的距离相等（使用平方距离避免浮点误差）。
   • 使用三重循环遍历所有可能的三元组。

4. 结果输出

   • 收集所有符合条件的字母，排序后输出。