C语言实现N*N矩阵重力下落及空列右移功能的算法咨询

你需要实现N*N矩阵的重力下落逻辑，包含两个核心规则：

• 列内非空元素向下沉降，空位留在列顶部
• 全空列由左侧非空列右移填补，最终所有非空列都靠矩阵右侧排列
  你现有实现不仅存在语法错误无法运行，逐元素移动的O(n³)逻辑性能也较差，以下是优化后的O(n²)实现方案。

1. 列内元素沉降处理 #

对每一列单独处理，仅需一次遍历即可完成所有元素下落：

• 从每列的底部开始向上遍历，收集所有非空元素
• 将收集到的元素从底到顶依次回填，剩余的顶部位置统一填充空值

2. 空列右移填补处理 #

所有列完成沉降后，处理全空列：

• 从矩阵最右侧列开始向左遍历，收集所有非全空的列
• 将收集到的列从右到左依次回填，剩余的左侧位置统一填充全空列

// 假设EMPTY已定义为非0~h-1范围内的值，比如#define EMPTY -1
void gravity(game_t *p) {
    int i, j, pos;
    int n = p->n;

    // 第一步：处理每一列的元素下落
    for (j = 0; j < n; j++) {
        pos = n - 1; // 指向当前列待填充的最底部空位
        // 从下往上遍历当前列，收集非空元素
        for (i = n - 1; i >= 0; i--) {
            if (p->board[i][j] != EMPTY) {
                p->board[pos][j] = p->board[i][j];
                // 避免同一个位置重复赋值的多余操作
                if (pos != i) {
                    p->board[i][j] = EMPTY;
                }
                pos--;
            }
        }
    }

    // 第二步：处理全空列，左侧非空列右移填补
    pos = n - 1; // 指向当前待填充的最右侧空列
    // 从右往左遍历所有列，收集非全空列
    for (j = n - 1; j >= 0; j--) {
        // 检查当前列是否为全空
        int is_empty_col = 1;
        for (i = 0; i < n; i++) {
            if (p->board[i][j] != EMPTY) {
                is_empty_col = 0;
                break;
            }
        }
        if (!is_empty_col) {
            // 非全空列复制到pos位置的列
            if (pos != j) {
                for (i = 0; i < n; i++) {
                    p->board[i][pos] = p->board[i][j];
                    p->board[i][j] = EMPTY;
                }
            }
            pos--;
        }
    }
}

• 时间复杂度为O(n²)，仅需遍历矩阵常数次，远优于原逐元素移动的O(n³)实现，不需要递归即可实现最优性能
• 逻辑分层清晰，先处理列内沉降再处理空列位移，便于后续调试和规则修改
• 避免了重复赋值等多余操作，进一步提升运行效率

内容的提问来源于stack exchange，提问作者PhysicsStudent