算法二：直方圖 + 單調棧 —— O(R×C) = 4000 (最優)

將每行視為直方圖底部，高度 = 連續 * 向上延伸的列數。經典「最大矩形面積」問題變體。

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

#define ROWS 50
#define COLS 80

bool detect_rectangle(char img[ROWS][COLS], int *out_r1, int *out_c1, int *out_r2, int *out_c2) {
    int height[COLS] = {0};
    int stack[COLS], top;

    for (int r = 0; r < ROWS; r++) {
        // 更新直方圖高度
        for (int c = 0; c < COLS; c++) {
            height[c] = (img[r][c] == '*') ? height[c] + 1 : 0;
        }

        // 單調遞增棧找最大矩形
        top = 0;
        for (int c = 0; c <= COLS; c++) {
            int h = (c == COLS) ? 0 : height[c];
            while (top > 0 && h < height[stack[top - 1]]) {
                int hh = height[stack[--top]];
                int left = (top == 0) ? 0 : stack[top - 1] + 1;
                int right = c - 1;
                int area = hh * (right - left + 1);
                if (area > 0) { // 找到非零矩形
                    *out_r1 = r - hh + 1;
                    *out_c1 = left;
                    *out_r2 = r;
                    *out_c2 = right;
                    return true;
                }
            }
            stack[top++] = c;
        }
    }
    return false;
}

算法三：前綴和 + 任意矩形 O(1) 查詢 —— O(R²C) = 2×10⁵ (工程實用)

預計算 2D 前綴和 sum[r][c] = (0,0) 到 (r,c) 的 * 總數。任意矩形 * 數 = sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1]。若等於面積則為全 * 矩形。

int sum[ROWS+1][COLS+1] = {0};
for (int r = 1; r <= ROWS; r++)
  for (int c = 1; c <= COLS; c++)
    sum[r][c] = sum[r-1][c] + sum[r][c-1] - sum[r-1][c-1] + (img[r-1][c-1] == '*');

for (int r1 = 1; r1 <= ROWS; r1++)
  for (int c1 = 1; c1 <= COLS; c1++)
    for (int r2 = r1; r2 <= ROWS; r2++)
      for (int c2 = c1; c2 <= COLS; c2++) {
        int stars = sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1];
        int area = (r2 - r1 + 1) * (c2 - c1 + 1);
        if (stars == area) return true;
      }

讀取輸入的關鍵細節

// 逐字符讀取，跳過行尾換行
for (int r = 0; r < ROWS; r++) {
    for (int c = 0; c < COLS; c++) {
        int ch = getchar();
        while (ch == '\n' || ch == '\r') ch = getchar(); // 吞掉換行
        img[r][c] = (char)ch;
    }
}

複雜度對比與選型建議

結語

字符矩陣矩形檢測是 2D 模式識別的入門問題。從暴力枚舉到直方圖單調棧，複雜度優化路徑清晰展示了「預計算 + 資料結構」的算法威力。C 語言的陣列佈局與指標運算極適合實現這類演算法，掌握前綴和、單調棧兩大通用技術，能解決從圖像處理、表格分析到遊戲地圖檢測的廣泛問題。