d365 - 10336 - Rank the Languages
題目描述
題目要求計算一個由小寫字母組成的矩陣中，每個字母所代表的連通區域的大小，並按照區域大小從大到小輸出每個字母及其對應的區域大小。如果多個字母的區域大小相同，則按照字母的字典序輸出。
解題思路
這題的核心是計算連通區域的大小。可以使用深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS) 來實現。程式碼中使用了 DFS。
- 讀取輸入，包括矩陣的行數和列數，以及矩陣本身。
- 建立一個
ans陣列，用於儲存每個字母出現的次數，初始化為 0。 - 遍歷矩陣，如果遇到未訪問過的字母，則調用 DFS 函數，計算該字母所代表的連通區域的大小，並將結果儲存在
ans陣列中。 - DFS 函數的目的是將與起始字母連通的所有相同字母的格子標記為已訪問（這裡用 '0' 標記），並遞迴地探索相鄰的格子。
- 遍歷
ans陣列，按照區域大小從大到小輸出每個字母及其對應的區域大小。如果多個字母的區域大小相同，則按照字母的字典序輸出。
複雜度分析
- 時間複雜度: O(H * W)，其中 H 是矩陣的行數，W 是矩陣的列數。因為需要遍歷整個矩陣，並且 DFS 最多訪問每個格子一次。
- 空間複雜度: O(H * W)，主要用於儲存矩陣
m和ans陣列。DFS 的遞迴深度在最壞情況下可能達到 H * W。
程式碼
#include <iostream>
using namespace std;
char m[100][100];
int ans[26];
void fps(int x,int y,int a,int b,char t){
m[x][y]='0';
if(x+1<a&&m[x+1][y]==t){
fps(x+1,y,a,b,m[x+1][y]);
}
if(x-1>=0&&m[x-1][y]==t){
fps(x-1,y,a,b,m[x-1][y]);
}
if(y+1<b&&m[x][y+1]==t){
fps(x,y+1,a,b,m[x][y+1]);
}
if(y-1>=0&&m[x][y-1]==t){
fps(x,y-1,a,b,m[x][y-1]);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,a,b;
cin >> n;
for(int i=1;i<=n;i++){
cout << "World #" << i << "\n";
cin >> a >> b;
int max=1;
for(int i=0;i<26;i++){
ans[i]=0;
}
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
cin >> m[i][j];
}
}
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
if(m[i][j]!='0'){
ans[m[i][j]-97]++;
fps(i,j,a,b,m[i][j]);
}
}
}
while(max>0){
max=0;
for(int i=0;i<26;i++){
if(ans[i]>max){
max=ans[i];
}
}
if(max==0)break;
for(int i=0;i<26;i++){
if(ans[i]==max){
char s=i+'a';
cout << s << ": " << max << "\n";
ans[i]=0;
}
}
}
}
}