資料結構 205 尋找圖中的隱藏秘密(難)

may

資料結構 205 尋找圖中的隱藏秘密
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 在一個古老的科學研究所中，研究員發現了一張神秘的二維二元圖像，這張圖像只包含黑色（由 0 組成）和白色（由 1 組成）。

(2) 據說，這個圖像中隱藏著一個重要的秘密：「最大的連續白色矩形區域（由 1 組成）」代表著一個神秘代碼的位置。為了解開這個秘密，研究員需要編寫一個程式來尋找這個「最大的連續白色矩形區域」。

提示：「最大的連續白色矩形區域」即為「最大矩形」，而且圖中只有唯一一個，其面積為組成該區域數字「1」的總數。

提示：程式由左至右，由上至下找尋。

3. 輸入輸出：
輸入說明
第 1 列：輸入 n、m 兩個正整數，代表二維圖像大小為 n * m。
第 2 ~ n + 1 列：每列輸入 m 個整數序列（由 0 和 1 組成），整數間以半形空白間隔。

輸出說明
第 1 列：輸出最大矩形面積。
第 2 列：輸出最大矩形面積左上角的位置座標。
第 3 列：輸出最大矩形面積右下角的位置座標。

範例輸入1
4 5
0 1 1 1 0
1 1 1 1 0
1 0 1 0 0
1 0 0 0 1
範例輸出1
6
(0, 1)
(1, 3)
範例輸入2
4 6
0 0 1 1 1 0
0 1 1 1 0 0
1 1 0 0 0 0
1 1 1 1 1 0
範例輸出2
5
(3, 0)
(3, 4)

may

1. //#include <iostream>
   
2. //#include <vector>
   
3. //#include <stack>
   
4. #include <bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. struct Result {
   
8.     int maxArea;
   
9.     int startRow, startCol;
   
10.     int endRow, endCol;
    
11. };
    
12. 
    
13. // 計算直方圖中的最大矩形面積
    
14. Result maxRectangleInHistogram(vector<int>& heights, int row) {
    
15.     stack<int> s;
    
16.     int maxArea = 0, left = 0, right = 0, topRow = row;
    
17.     vector<int> leftBoundary(heights.size()), rightBoundary(heights.size());
    
18. 
    
19.     // 計算左邊界
    
20.     for (int i = 0; i < heights.size(); i++) {
    
21.         while (!s.empty() && heights[s.top()] >= heights[i]) s.pop();
    
22.         leftBoundary[i] = s.empty() ? 0 : s.top() + 1;
    
23.         s.push(i);
    
24.     }
    
25. 
    
26.     // 清空棧，計算右邊界
    
27.     while (!s.empty()) s.pop();
    
28.     for (int i = heights.size() - 1; i >= 0; i--) {
    
29.         while (!s.empty() && heights[s.top()] >= heights[i]) s.pop();
    
30.         rightBoundary[i] = s.empty() ? heights.size() - 1 : s.top() - 1;
    
31.         s.push(i);
    
32.     }
    
33. 
    
34.     // 計算最大面積
    
35.     for (int i = 0; i < heights.size(); i++) {
    
36.         int area = heights[i] * (rightBoundary[i] - leftBoundary[i] + 1);
    
37.         if (area > maxArea) {
    
38.             maxArea = area;
    
39.             left = leftBoundary[i];
    
40.             right = rightBoundary[i];
    
41.             topRow = row - heights[i] + 1;  // 修正 topRow 計算方式
    
42.         }
    
43.     }
    
44. 
    
45.     return {maxArea, topRow, left, row, right};
    
46. }
    
47. 
    
48. // 找到最大的連續白色矩形
    
49. void findLargestWhiteRectangle(vector<vector<int>>& matrix) {
    
50.     int n = matrix.size(), m = matrix[0].size();
    
51.     vector<int> heights(m, 0);
    
52.     int maxArea = 0, startRow = 0, startCol = 0, endRow = 0, endCol = 0;
    
53. 
    
54.     for (int i = 0; i < n; i++) {
    
55.         // 更新直方圖高度
    
56.         for (int j = 0; j < m; j++) {
    
57.             heights[j] = (matrix[i][j] == 0) ? 0 : heights[j] + 1;
    
58.         }
    
59. 
    
60.         // 計算當前行作為底部時的最大矩形
    
61.         Result res = maxRectangleInHistogram(heights, i);
    
62.         if (res.maxArea > maxArea) {
    
63.             maxArea = res.maxArea;
    
64.             startRow = res.startRow;
    
65.             startCol = res.startCol;
    
66.             endRow = res.endRow;
    
67.             endCol = res.endCol;
    
68.         }
    
69.     }
    
70. 
    
71.     // 輸出結果
    
72.     cout << maxArea << endl;
    
73.     cout << "(" << startRow << ", " << startCol << ")" << endl;
    
74.     cout << "(" << endRow << ", " << endCol << ")" << endl;
    
75. }
    
76. 
    
77. int main() {
    
78.     int n, m;
    
79.     cin >> n >> m;
    
80.     vector<vector<int>> matrix(n, vector<int>(m));
    
81. 
    
82.     // 讀取輸入
    
83.     for (int i = 0; i < n; i++)
    
84.         for (int j = 0; j < m; j++)
    
85.             cin >> matrix[i][j];
    
86. 
    
87.     // 查找最大矩形
    
88.     findLargestWhiteRectangle(matrix);
    
89. 
    
90.     return 0;
    
91. }

複製代碼

回復 1# may
-----------------------------------------------
解釋程式碼
輸入讀取：

讀取 n（行數）和 m（列數）。

讀取 n × m 的矩陣數據。

計算直方圖高度：

用 heights 陣列來記錄每一列的高度，遇到 0 則該列重置為 0，否則累加高度。

使用單調棧計算最大矩形面積：

maxRectangleInHistogram 函式：

計算每列的 左邊界 和 右邊界。

計算當前行作為底部時的最大矩形面積。
startRow 計算方式應該根據 heights 陣列來回溯計算矩形的上邊界，而不是單純地假設當前行是起點。

追蹤最大矩形位置：

當發現更大的矩形時，更新 startRow, startCol, endRow, endCol。

輸出結果

依題目要求輸出面積、左上角座標 (startRow, startCol)，右下角座標 (endRow, endCol)。
-------------------------------------------------------------------
測資:
測試00：基礎測試 (範例 1)
輸入
4 5
0 1 1 1 0
1 1 1 1 0
1 0 1 0 0
1 0 0 0 1
預期輸出
6
(0, 1)
(1, 3)
測試 01：範例 2
輸入
4 6
0 0 1 1 1 0
0 1 1 1 0 0
1 1 0 0 0 0
1 1 1 1 1 0
預期輸出
5
(3, 0)
(3, 4)
測試 02：整個矩陣都是 1
輸入
3 4
1 1 1 1
1 1 1 1
1 1 1 1
預期輸出
12
(0, 0)
(2, 3)
測試03：無法形成大矩形
輸入
5 5
0 0 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 0 0
預期輸出
3
(3, 1)
(3, 3)
測試 04：多個矩形但其中一個最大
輸入
6 7
1 1 0 0 1 1 1
1 1 0 0 1 1 1
0 0 1 1 1 0 0
0 0 1 1 1 0 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
預期輸出
14
(4, 0)
(5, 6)
這 5 筆測資涵蓋：

基礎範例測試

極端情況 (全部為 1 或無法形成大矩形)

多個可能解但需選擇最大者