返回列表 發帖

Rank: 9Rank: 9Rank: 9
1# 跳轉到 » 倒序看帖
打印
tT
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

Rank: 9Rank: 9Rank: 9
2#
may發表於 2025-3-25 12:59 | 只看該作者
  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <stack>
  4. #include <bits/stdc++.h>
  5. using namespace std;

  7. struct Result {
  8.     int maxArea;
  9.     int startRow, startCol;
  10.     int endRow, endCol;
  11. };

  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());

  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.     }

  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.     }

  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.     }

  45.     return {maxArea, topRow, left, row, right};
  46. }

  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;

  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.         }

  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.     }

  71.     // 輸出結果
  72.     cout << maxArea << endl;
  73.     cout << "(" << startRow << ", " << startCol << ")" << endl;
  74.     cout << "(" << endRow << ", " << endCol << ")" << endl;
  75. }

  77. int main() {
  78.     int n, m;
  79.     cin >> n >> m;
  80.     vector<vector<int>> matrix(n, vector<int>(m));

  82.     // 讀取輸入
  83.     for (int i = 0; i < n; i++)
  84.         for (int j = 0; j < m; j++)
  85.             cin >> matrix[i][j];

  87.     // 查找最大矩形
  88.     findLargestWhiteRectangle(matrix);

  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 或無法形成大矩形)

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

TOP

返回列表