標題:
資料結構 205 尋找圖中的隱藏秘密(難)
[打印本頁]
作者:
may
時間:
2025-3-25 12:37
標題:
資料結構 205 尋找圖中的隱藏秘密(難)
資料結構 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
時間:
2025-3-25 12:59
//#include <iostream>
//#include <vector>
//#include <stack>
#include <bits/stdc++.h>
using namespace std;
struct Result {
int maxArea;
int startRow, startCol;
int endRow, endCol;
};
// 計算直方圖中的最大矩形面積
Result maxRectangleInHistogram(vector<int>& heights, int row) {
stack<int> s;
int maxArea = 0, left = 0, right = 0, topRow = row;
vector<int> leftBoundary(heights.size()), rightBoundary(heights.size());
// 計算左邊界
for (int i = 0; i < heights.size(); i++) {
while (!s.empty() && heights[s.top()] >= heights[i]) s.pop();
leftBoundary[i] = s.empty() ? 0 : s.top() + 1;
s.push(i);
}
// 清空棧，計算右邊界
while (!s.empty()) s.pop();
for (int i = heights.size() - 1; i >= 0; i--) {
while (!s.empty() && heights[s.top()] >= heights[i]) s.pop();
rightBoundary[i] = s.empty() ? heights.size() - 1 : s.top() - 1;
s.push(i);
}
// 計算最大面積
for (int i = 0; i < heights.size(); i++) {
int area = heights[i] * (rightBoundary[i] - leftBoundary[i] + 1);
if (area > maxArea) {
maxArea = area;
left = leftBoundary[i];
right = rightBoundary[i];
topRow = row - heights[i] + 1; // 修正 topRow 計算方式
}
}
return {maxArea, topRow, left, row, right};
}
// 找到最大的連續白色矩形
void findLargestWhiteRectangle(vector<vector<int>>& matrix) {
int n = matrix.size(), m = matrix[0].size();
vector<int> heights(m, 0);
int maxArea = 0, startRow = 0, startCol = 0, endRow = 0, endCol = 0;
for (int i = 0; i < n; i++) {
// 更新直方圖高度
for (int j = 0; j < m; j++) {
heights[j] = (matrix[i][j] == 0) ? 0 : heights[j] + 1;
}
// 計算當前行作為底部時的最大矩形
Result res = maxRectangleInHistogram(heights, i);
if (res.maxArea > maxArea) {
maxArea = res.maxArea;
startRow = res.startRow;
startCol = res.startCol;
endRow = res.endRow;
endCol = res.endCol;
}
}
// 輸出結果
cout << maxArea << endl;
cout << "(" << startRow << ", " << startCol << ")" << endl;
cout << "(" << endRow << ", " << endCol << ")" << endl;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> matrix(n, vector<int>(m));
// 讀取輸入
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> matrix[i][j];
// 查找最大矩形
findLargestWhiteRectangle(matrix);
return 0;
}
複製代碼
回復
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 或無法形成大矩形)
多個可能解但需選擇最大者
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2
