C語言經典算法題：二維數組鞍點查找完整解析

問題定義

在 m×n 矩陣中尋找「鞍點」：該位置元素在所在行最大、所在列最小。下標從 0 開始。輸出格式 Array[i][j]=x，不存在輸出 None。保證至多一個鞍點。

算法思路

1. 讀入矩陣維度與元素。
2. 遍歷每一行，找出該行最大值及其列索引 col。
3. 檢查該值是否為所在列 col 的最小值：遍歷所有行比較 matrix[row][col]。
4. 若滿足條件輸出並結束；全部行檢查完無結果則輸出 None。

時間複雜度 O(m×n)，空間複雜度 O(1) 額外空間。

原始代碼邏輯缺陷與修正

• 列最小值判定錯誤：原代碼 if(k <= num[l][y]) flag=1 邏輯反了，應檢查 k 是否 小於等於 所有列元素，即 k <= num[l][y] 對所有 l 成立。但原代碼一旦發現 k > num[l][y] 即 break 並 flag=0，這部分邏輯其實正確。
• 行最大值初始化：每行重置 k = num[i][0] 正確。
• 多測試用例處理：while(scanf(...)!=EOF) 正確支援多組輸入。

優化版代碼（含註釋與邊界檢查）

#include <stdio.h>
#include <stdbool.h>

#define MAX_DIM 10

int main() {
    int m, n;
    int matrix[MAX_DIM][MAX_DIM];

    while (scanf("%d %d", &n, &m) == 2) { // n rows, m cols
        if (n <= 0 || n > MAX_DIM || m <= 0 || m > MAX_DIM) {
            printf("Invalid dimensions\n");
            continue;
        }
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &matrix[i][j]);

        bool found = false;
        for (int i = 0; i < n && !found; i++) {
            // 找第 i 行最大值及其列
            int max_val = matrix[i][0], col = 0;
            for (int j = 1; j < m; j++) {
                if (matrix[i][j] > max_val) {
                    max_val = matrix[i][j];
                    col = j;
                }
            }
            // 檢查是否為第 col 列最小值
            bool is_min = true;
            for (int r = 0; r < n; r++) {
                if (matrix[r][col] < max_val) { is_min = false; break; }
            }
            if (is_min) {
                printf("Array[%d][%d]=%d\n", i, col, max_val);
                found = true;
            }
        }
        if (!found) printf("None\n");
    }
    return 0;
}

測試用例驗證

Input:
3 3
1 2 3
4 5 6
7 8 9

Output:
Array[0][2]=3
// 第 0 行最大 3 (col=2)，第 2 列元素為 3,6,9，最小為 3，滿足條件

進階變體與擴展

1. 多鞍點輸出：移除 found 中斷，收集所有鞍點輸出。
2. 隨機矩陣生成測試：編寫 Python 腳本生成大規模測試資料，驗證算法正確性與效能。
3. 分治優化：對於超大矩陣，可預計算每行最大值與每列最小值陣列，查找時 O(1) 判斷，總複雜度仍 O(mn) 但常數因子更小。
4. 鞍點博弈論意義：零和博弈中鞍點對應納什均衡，可延伸至博弈論求解器開發。