題目描述

編程計算由“*”號圍成的下列圖形的面積。面積計算方法是統計*號所圍成的閉合曲線中水平線和垂直線交點的數目。如下圖所示，在10×10的二維數組中，有“*”圍住了15個點，因此面積為15。

輸入

10×10的圖形。

輸出

輸出面積。

樣例

輸入數據 1

0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0

輸出數據 1

15

來源

一本通在線評測

圍成面積問題思路

問題分析：

計算由''字符圍成的閉合區域面積，實際是統計被''包圍的空白點數量。

核心思路：??洪水填充法（Flood Fill）??

從邊界開始向外擴散，標記所有能夠到達的空白點，剩下的未被標記的空白點就是被包圍的區域。

具體步驟：

1. 1.

   ??預處理??：

   • ?將輸入數據存儲在10×10的字符矩陣中
   • ?在矩陣外圍添加一圈空白（作為邊界起點）
2. 2.

   ??邊界洪水填充??：

   • ?從四個角點開始進行BFS/DFS遍歷
   • ?將所有與邊界連通的空白點標記為已訪問
3. 3.

   ??統計內部空白點??：

   • ?遍歷整個矩陣（不包括外圍添加的邊界）
   • ?統計未被標記的空白點數量（這些就是被'*'包圍的區域）
4. 4.

   ??輸出結果??：

   • ?內部空白點數量即為所求面積

算法選擇：

• ???BFS（廣度優先搜索）??：更適合矩陣遍歷，避免遞歸深度問題
• ???方向處理??：四個方向（上、下、左、右）移動

關鍵點：

1. 1.??外圍擴展??：在10×10矩陣外添加一圈，確保能從邊界開始填充
2. 2.??標記機制??：使用visited數組記錄可達點
3. 3.??邊界條件??：只處理空白點（非''字符），遇到''則停止擴散

復雜度分析：

• ?時間復雜度：O(n2) = O(100)
• ?空間復雜度：O(n2) = O(100)

示例驗證：

對于樣例輸入，通過洪水填充后，內部未被標記的空白點正好是15個，與題目描述一致。

這種方法能夠準確識別閉合區域，適用于各種形狀的包圍情況。

代碼樣例

#include<bits/stdc++.h>
using namespace std;char mp[12][12];
bool vis[12][12];
int dx[]= {0,0,1,-1};
int dy[]= {1,-1,0,0};void dfs(int x,int y)
{if(x<0 || x>11 || y<0 || y>11){return;}if(vis[x][y] || mp[x][y]=='1'){return;}vis[x][y]=1;for(int i=0; i<4; i++){dfs(x+dx[i],y+dy[i]);}
}int main()
{for(int i=0; i<12; i++){for(int j=0; j<12; j++){mp[i][j]='0';}}for(int i=1; i<=10; i++){for(int j=1; j<=10; j++){cin>>mp[i][j];}}dfs(0,0);int cnt=0;for(int i=1; i<=10; i++){for(int j=1; j<=10; j++){if(!vis[i][j] && mp[i][j]=='0'){cnt++;}}}cout<<cnt;return 0;
}

此代碼僅供參考，請勿純抄