a753 - 一、最大面積
題目描述
題目要求在一個給定的矩陣中，找出特定高度 H 的最大連續區域面積。連續區域的定義是相鄰的格子高度等於 H，且任一格子至少與其上下左右四個格子中的一個高度相等。如果連續區域面積小於 2，則輸出 0。
解題思路
程式碼使用深度優先搜尋 (DFS) 來尋找連續區域。dfs 函數從一個給定的格子開始，如果該格子的高度等於目標高度 n，則將其標記為已訪問 (設為 0)，並遞迴地訪問其相鄰的格子。count 變數用於追蹤當前連續區域的大小。對於每個不同的高度 n，t[n] 儲存找到的最大連續區域面積。主程式首先讀取矩陣，然後對每個不同的高度執行 DFS，更新 t[n]。最後，程式讀取要查詢的高度列表，並輸出對應的最大連續區域面積。
複雜度分析
- 時間複雜度: O(A * B * C)，其中 A 和 B 是矩陣的尺寸，C 是查詢的高度數量。在最壞的情況下，DFS 可能需要遍歷整個矩陣，並且對於每個查詢的高度，都需要執行一次 DFS。
- 空間複雜度: O(A * B)，主要用於儲存矩陣
k和t陣列。DFS 的遞迴深度在最壞情況下可能達到 A * B。
程式碼
#include <iostream>
using namespace std;
int k[32][32],t[10],count=0;
void dfs(int x,int y,int n){
count++;
k[x][y]=0;
if(k[x+1][y]==n){
dfs(x+1,y,n);
}
if(k[x][y+1]==n){
dfs(x,y+1,n);
}
if(x-1>=0&&k[x-1][y]==n){
dfs(x-1,y,n);
}
if(y-1>=0&&k[x][y-1]==n){
dfs(x,y-1,n);
}
}
int main(){
int a,b;
cin >> a >> b;
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
cin >> k[i][j];
}
}
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
if(k[i][j]!=0){
int tmp=k[i][j];
dfs(i,j,k[i][j]);
if(count>t[tmp]){
t[tmp]=count;
}
count=0;
}
}
}
cin >> a;
while(a--){
cin >> b;
if(t[b]<2){
cout << "0\n";
}
else{
cout << t[b] << "\n";
}
}
}