这是一道结合了回溯算法与路径模拟的题目。我们需要枚举每个棋子的所有可能移动方案（方向+步数），然后模拟时间轴来检查是否存在碰撞。
以下是完整的 C 语言实现代码。
解题思路
1. 方向定义：将棋盘移动抽象为 8 个方向（上、下、左、右、左上、右上、左下、右下）。
2. 移动生成：对于每个棋子，根据其类型（车、后、象）确定合法方向，并计算每个方向上能走的最大步数（不能出界）。
3. 回溯 (DFS)：递归地为每个棋子选择一个移动方案（方向+步数，或者不动）。
4. 冲突检测：当所有棋子都选完方案后，模拟每一秒的移动。
* 对于每一秒 t，计算每个棋子的位置。
* 如果棋子还没走完，位置 = 起点 + t times 方向。
* 如果棋子已经走完，位置 = 终点。
* 检查该时刻是否有两个棋子在同一格。
C 语言代码实现
include
include
include
include
// 定义方向数组：0-3为上下左右，4-7为四个斜向
// 对应：右, 下, 左, 上, 右下, 左下, 右上, 左上
int dirs[8][2] = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0},
{1, 1}, {1, -1}, {-1, 1}, {-1, -1}
};
// 存储单个棋子的移动方案
typedef struct {
int dir_idx; // 方向索引 (-1 表示不动)
int steps; // 步数
} Move;
// 获取棋子对应的方向索引列表
int get_directions(const char* piece, int* out_dirs) {
int count = 0;
if (strcmp(piece, "rook") == 0) {
// 车：0, 1, 2, 3
for (int i = 0; i max_time) max_time = moves[i].steps;
}
// 逐秒模拟
for (int t = 1; t = 0 && nr = 0 && nc < 8) {
all_moves[i][count++] = (Move){dir_idx, step};
} else {
break; // 出界，该方向后续步数也不合法
}
}
}
all_moves_count[i] = count;
}
// 3. 开始回溯
int result = dfs(0, current_moves, all_moves, all_moves_count, positions, n);
// 4. 释放内存
for (int i = 0; i < n; i++) free(all_moves[i]);
free(all_moves);
free(all_moves_count);
free(current_moves);
return result;
}
代码关键点解析
1. 坐标转换：
题目给出的坐标是 1-based (1~8)，C 语言数组通常是 0-based。所以在开始时将 positions 全部减 1，计算完后再还原（或者直接在逻辑中处理，这里选择预处理减 1）。
2. 移动方案存储 (Move 结构体)：
我们不仅存储终点，而是存储 (方向索引, 步数)。
* dir_idx = -1 表示不动。
* 这样在模拟时，我们可以根据时间 t 动态计算位置。
3. 冲突检测 (is_valid)：
这是核心逻辑。
* 我们需要模拟从 t=1 到 t=max(text{steps}) 的过程。
* 对于每个时刻 t，如果棋子的计划步数 S ge t，它就在移动中；如果 S < t，它已经停在终点。
* 使用 board[8][8] 数组来快速检测同一时刻是否有多个棋子落在同一格。
4. 交换位置的处理：
题目提到“如果两个棋子直接相邻且下一秒互相占据对方位置”是允许的。
* 例如 A 在 (0,0) 去 (0,1)，B 在 (0,1) 去 (0,0)。
* t=1 时，A 在 (0,1)，B 在 (0,0)。
* 我们的模拟逻辑中，分别计算 A 和 B 在 t=1 的位置，发现它们互换了，且没有重叠，因此判定为合法。逻辑天然支持此情况。
针对 LeetCode 2056 这道题，C 语言代码的性能瓶颈通常不在于算法逻辑（因为数据范围极小，N le 4），而在于内存管理和指令开销。
以下是针对 C 语言实现的三个关键优化方向，按效果从高到低排序：
1. 消除动态内存分配 (最关键)
原代码在 countCombinations 中使用了 malloc 来为每个棋子分配移动方案数组。在 LeetCode 的评测环境中，频繁的堆内存分配（malloc/free）非常耗时。
优化方案：
由于棋盘只有 8 times 8，每个棋子最多只有 8 个方向，每个方向最多走 7 步。
单个棋子的最大移动方案数 = 1 (不动) + 8 (方向) times 7 (步数) = 57 种。
我们可以直接使用静态数组或栈内存，完全避免 malloc。
2. 使用位运算进行碰撞检测
原代码使用 int board[8][8] 来检测碰撞。每次模拟都需要 memset 清零，然后进行二维数组寻址。
优化方案：
8 times 8 的棋盘正好可以用 64位整数 (long long) 表示。
- 棋盘的第 r 行第 c 列对应整数的第 r times 8 + c 位。
- 检测碰撞变成了位运算：if (current_mask & time_mask) != 0。
- 这不仅消除了 memset，还让碰撞检测变成了单条 CPU 指令。
3. 预计算方向数组
在循环中通过 strcmp 判断棋子类型并获取方向是重复劳动。可以在函数开始时一次性解析好每个棋子的合法方向列表。
🚀 优化后的 C 语言代码 (高性能版)
include
include
include
include
// 定义方向：右, 下, 左, 上, 右下, 左下, 右上, 左上
static const int DIRS[8][2] = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0},
{1, 1}, {1, -1}, {-1, 1}, {-1, -1}
};
// 移动方案结构体
typedef struct {
int dir_idx; // 方向索引 (-1 表示不动)
int steps; // 步数
} Move;
// 全局变量用于回溯，避免参数传递开销
static int g_result = 0;
static Move g_current_moves[4]; // 最多4个棋子
static Move g_all_moves[4][60]; // 预分配静态内存：4个棋子 * 60个方案
static int g_moves_count[4];
static int g_positions[4][2]; // 本地缓存位置
// 核心优化：使用 long long 作为位图表示棋盘 (8x8 = 64 bits)
// 第 r 行 c 列 对应位: (r max_time)
max_time = g_current_moves[i].steps;
}
// 逐秒模拟
for (int t = 1; t = 0 && nr = 0 && nc < 8) {
g_all_moves[i][g_moves_count[i]++] = (Move){d, step};
} else {
break;
}
}
}
}
// 2. 开始回溯
dfs(0, n);
return g_result;
}
性能对比分析
优化点 原始代码 优化后代码 提升原因
内存分配 malloc / free 静态数组 避免了系统调用开销，内存访问局部性更好。
碰撞检测 int board[8][8] + memset long long 位运算 将 O(64) 的清零和查找操作降低为 O(1) 的寄存器操作。
全局状态 参数传递 全局变量 减少了递归调用时的栈帧参数复制开销（虽然编译器可能会优化，但在 C 中显式声明更安全）。
方向解析 每次 DFS 内部判断 预处理 将字符串比较移出了最耗时的 DFS 循环。
这种写法在 LeetCode 上通常能达到 0ms 或 接近 0ms 的运行时间。
