Board logo

標題: 資料結構 104 找出最大的低窪區域(中) [打印本頁]
作者: may    時間: 2025-3-23 18:18     標題: 資料結構 104 找出最大的低窪區域(中)

資料結構 104 找出最大的低窪區域

1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 市政府想要利用空拍影像來找出全市可能的淹水區域，目前市政府已經完成空拍、並將空拍影像劃分為小區塊，每個小區塊的面積皆為 1，再根據各區域的平均地勢高低標示出可能淹水的程度：0 ~ 5；其中「0」就是地勢最低的低窪區域（幾乎每次下大雨必淹的區塊），而「5」則為地勢最高的區域。

(2) 那些相連的低窪區塊就是需要投入經費來整治的區域，目前市政府團隊希望能優先處理影響最大的低窪區域。請你幫忙寫一支程式讀取空拍圖資區塊資料，並找出最大的相連低窪區域面積。

提示：建議使用二維陣列來處理資料。

注意：連續相連的低窪區塊的「相連」是指某區塊的上、下、左、右的區塊，但不列計斜對角。

3. 輸入輸出：
輸入說明
第 1 列：由半形空白間隔的兩個正整數 M、N，表示縱向與橫向的小區域數量（5 ≤ M, N ≤ 100）。
第 2~M+1 列：每一列有 N 個由半形空白間隔的數字（0 ~ 5）。其中，「0」代表會淹水的低窪區域，其他數字（1 ~ 5）則表示較不容易發生淹水的區域。

輸出說明
最大的相連低窪區域面積，若沒有低窪區域，則輸出「0」。

範例輸入1
6 6
3 2 3 2 3 3
2 0 0 0 2 2
2 0 1 0 0 3
3 0 0 2 2 3
2 0 0 0 0 2
3 2 3 2 2 3
範例輸出1
12
範例輸入2
10 8
3 0 0 0 0 0 0 0
2 2 2 2 2 2 2 0
3 3 2 0 0 2 2 0
0 1 0 0 0 0 2 0
0 1 2 2 2 0 2 0
0 1 0 2 2 0 2 0
0 1 0 0 0 0 2 0
0 1 2 0 0 2 2 0
0 1 2 2 2 2 2 0
0 0 0 0 0 0 0 0
範例輸出2
29
作者: may    時間: 2025-3-23 18:23

  1. //#include <iostream>
  2. //#include <vector>
  3. #include <bits/stdc++.h>
  4. using namespace std;

  6. int M, N;
  7. vector<vector<int>> grid;
  8. vector<vector<bool>> visited;
  9. int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上、下、左、右

  11. // 深度優先搜尋（DFS）來計算連通區域面積
  12. int dfs(int x, int y) {
  13.     if (x < 0 || x >= M || y < 0 || y >= N || grid[x][y] != 0 || visited[x][y]) {
  14.         return 0;
  15.     }
  16.    
  17.     visited[x][y] = true; // 標記已訪問
  18.     int area = 1; // 計算當前區域的大小
  19.    
  20.     // 搜尋四個方向
  21.     for (int i = 0; i < 4; i++) {
  22.         int newX = x + directions[i][0];
  23.         int newY = y + directions[i][1];
  24.         area += dfs(newX, newY);
  25.     }
  26.    
  27.     return area;
  28. }

  30. int main() {
  31.     // 讀取 M 和 N
  32.     cin >> M >> N;
  33.    
  34.     grid.assign(M, vector<int>(N));
  35.     visited.assign(M, vector<bool>(N, false));
  36.    
  37.     // 讀取 M × N 的地形資料
  38.     for (int i = 0; i < M; i++) {
  39.         for (int j = 0; j < N; j++) {
  40.             cin >> grid[i][j];
  41.         }
  42.     }
  43.    
  44.     int maxArea = 0;

  46.     // 遍歷所有的點
  47.     for (int i = 0; i < M; i++) {
  48.         for (int j = 0; j < N; j++) {
  49.             if (grid[i][j] == 0 && !visited[i][j]) {
  50.                 // 找到新的低窪區域，使用 DFS 搜索
  51.                 maxArea = max(maxArea, dfs(i, j));
  52.             }
  53.         }
  54.     }

  56.     // 輸出最大的低窪區域面積
  57.     cout << maxArea << endl;

  59.     return 0;
  60. }
複製代碼
回復 1# may
-------------------------------------------------------
解題思路
輸入資料：

讀取 M（縱向大小）和 N（橫向大小）。

讀取 M × N 的二維陣列，代表地勢高度。

遍歷陣列，尋找低窪區域 (0)：

若該格為 0，則用 DFS 或 BFS 搜尋其相連的 0，並統計區域大小。

搜尋相連區域：

透過 DFS 或 BFS 往 上、下、左、右 方向擴展。

標記已訪問的位置，以避免重複計算。

更新最大低窪區域面積：

每次找到一塊低窪區域，與當前最大值比較並更新。
-------------------------------------------------
測資:
測資00（基本測試）
輸入
5 5
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1
輸出
6
說明
0 形成一個 6 格大小的區域，最大低窪區域面積為 6。

測資01（多個低窪區域，取最大）
輸入
1 1 1 1 1 1 1
1 0 0 1 0 0 1
1 0 1 1 1 0 1
1 0 1 0 0 0 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
輸出
5
說明
共有 3 個低窪區域：

(1,1) ~ (3,1) 共 4 格

(1,4) ~ (1,5) 共 2 格

(3,4) ~ (4,3) ~ (4,4) 共 5 格

最大的區域面積為 5。

測資 02（全為高地，沒有低窪區域）
輸入
4 4
1 2 3 4
2 3 4 5
3 4 5 4
4 5 4 3
輸出
0
說明
沒有 0，所以輸出 0。

測資03（邊界低窪區域）
輸入
7 7
0 0 1 1 1 1 1
0 1 1 1 1 1 1
1 1 1 0 0 0 1
1 1 1 0 1 0 1
1 0 0 0 1 0 1
1 0 1 1 1 1 1
1 1 1 1 1 1 1
輸出
6
說明
左上角 (0,0) ~ (1,0) 形成一個 2 格低窪區域。

中間 (2,3) ~ (4,3) ~ (4,4) ~ (3,3) 共 6 格 形成最大區域。

測資 04（大範圍低窪區域）
輸入
8 8
1 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 0 0 0 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
輸出
9
說明
(1,1) ~ (1,3) + (2,1) + (2,3) + (3,1) ~ (3,4) + (4,4) ~ (6,4) 共 9 格

最大的低窪區域面積為 9。

這些測資涵蓋了：

基本情況

多個低窪區域，測試最大值

無低窪區域（邊界條件）

邊界上的低窪區域

較大連通低窪區域的測試

這些測資可以幫助驗證 演算法的正確性與邊界情況，確保程式能正確計算出最大低窪區域的面積！



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2