a597 - 祖靈被榨乾了!!!!!!!!
題目描述
題目描述了一個有趣的場景，要求計算一個二維矩陣中連通的 'J' 字元的數量（即 JIZZ 的攤數）以及最大攤位的面積。矩陣表示祖靈房間的平面圖，'J' 代表 JIZZ，'X' 代表沒有 JIZZ 的位置。連通定義為上下左右相鄰的 'J' 字元。
解題思路
本題可以使用廣度優先搜尋 (BFS) 來解決。遍歷矩陣，每當遇到一個 'J' 字元，就啟動一次 BFS，將其相鄰的 'J' 字元加入佇列，並將它們標記為已訪問（例如，將其值改為 'X'）。每次 BFS 完成，就表示找到了一攤 JIZZ，計算該攤 JIZZ 的大小，並更新最大攤位的面積。重複此過程，直到遍歷完整個矩陣。最後，輸出 JIZZ 的總攤數和最大攤位的面積。
複雜度分析
- 時間複雜度: O(m * n)，其中 m 和 n 分別是矩陣的行數和列數。因為每個單元格最多被訪問一次。
- 空間複雜度: O(m * n)，在最壞的情況下，整個矩陣都是 'J' 字元，BFS 佇列可能需要存儲所有單元格。
程式碼
#include <iostream>
#include <queue>
using namespace std;
int m,n,tmp,ans,total,to;
bool mp[501][501];
char c[501];
int main(){
while(scanf("%d %d",&m,&n)>0){
ans=tmp=total=to=0;
queue < pair<int,int> > q;
for(int i=0;i<m;++i){
scanf("%s",&c);
for(int j=0;j<n;++j){
if(c[j]=='J'){
mp[i][j]=1;
++to;
}
else
mp[i][j]=0;
}
}
if(m*n-to<min(m,n)){
printf("1 %d\n",to);
}
else{
for(int i=0;i<m;++i){
for(int j=0;j<n;++j){
if(mp[i][j]){
++total;
tmp=1;
q.push(make_pair(i,j));
while(q.empty()==0){
pair <int,int> p=q.front();
q.pop();
int x=p.first,y=p.second;
mp[x][y]=0;
if(x>0&&mp[x-1][y]){
q.push(make_pair(x-1,y));
mp[x-1][y]=0;
++tmp;
}
if(x<m-1&&mp[x+1][y]){
q.push(make_pair(x+1,y));
mp[x+1][y]=0;
++tmp;
}
if(y>0&&mp[x][y-1]){
q.push(make_pair(x,y-1));
mp[x][y-1]=0;
++tmp;
}
if(y<n-1&&mp[x][y+1]){
q.push(make_pair(x,y+1));
mp[x][y+1]=0;
++tmp;
}
}
ans=max(ans,tmp);
}
}
}
printf("%d %d\n",total,ans);
}
}
}