题意分析

问题背景

• 有一个 n×n 的方形插头（Plug）和插座（Socket），每个插头引脚和插座孔按**行主序（Row-Major Order）**编号（1到n²）。
• 插座可以旋转（0°、90°、180°、270°） 和 翻转（正面/反面），共 8种可能的配置。
• 给定 m 对连接关系（插头引脚 → 插座孔），要求在这些配置中，找到平均连接线长最小的方案。
• 连接线长计算方式：曼哈顿距离 + 1（因为布线块厚度）。

关键点

1. 位置映射：插座的旋转和翻转会改变孔的位置编号，需要计算每种配置下插座孔的坐标。
2. 距离计算：对于每对连接（pin → hole），计算其在当前配置下的曼哈顿距离。
3. 最优解：遍历所有8种配置，计算每种配置的平均距离，取最小值。

解题思路

步骤1：坐标转换

• 插头和插座的编号是 1 到 n²，但计算距离需要 二维坐标 (x, y)。
• 对于编号 k（1-based），其在 n×n 矩阵中的坐标为：

  x = (k - 1) / n;  // 行号（0-based）
  y = (k - 1) % n;  // 列号（0-based）
  

步骤2：枚举所有插座配置

插座有 8 种可能的配置（4种旋转 × 2种翻转）：

1. 不旋转 + 不翻转（原始配置）
2. 旋转90° + 不翻转
3. 旋转180° + 不翻转
4. 旋转270° + 不翻转
5. 不旋转 + 翻转（水平或垂直翻转）
6. 旋转90° + 翻转
7. 旋转180° + 翻转
8. 旋转270° + 翻转

步骤3：计算每种配置的映射

对于每种配置，计算插座孔的新坐标：

• 旋转角度：
  • 0°：(x, y)
  • 90°：(y, n-1 - x)
  • 180°：(n-1 - x, n-1 - y)
  • 270°：(n-1 - y, x)
• 翻转：
  • 水平翻转：(x, n-1 - y)
  • 垂直翻转：(n-1 - x, y)

步骤4：计算曼哈顿距离

对于每对连接 (pin, hole)：

1. 插头引脚 pin 的坐标 (x1, y1)。
2. 插座孔 hole 在当前配置下的坐标 (x2, y2)。
3. 曼哈顿距离：|x1 - x2| + |y1 - y2| + 1（+1 是布线块厚度）。

步骤5：计算平均距离

• 对每种配置，计算所有连接对的曼哈顿距离之和，再除以 m 得到平均距离。
• 最终取所有配置中的最小平均距离。