首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com
解題心得
直覺就是DFS，所以我就來解了
DFS真的讓人又愛又恨…<3
喔對了我學到”map以value排序的技巧”
然後又複習了map跟vector的clear()(每次都忘)
當然這題也不一定需要用到map
解題想法
DFS，沒啥好說的，因為我不會BFS…
這題麻煩的點有以下兩點:
1.紀錄後output部分是以區域數大小排序，相同則英文字母順序
2.單組有好多筆所以要清空前面的東西
先來說說我一開始的擔憂
我直覺使用map，但這就必須使用到”map以value排序”
map預設是使用key排序的，所以我就去爬文了.w.
後來找到用vector搭配pair並作自定義sort(不難喔)
接下來我又有個擔憂了，因為我本身不會算時間複雜度..
所以我就在想每一次都需要清空map跟vector，這樣會不會超時
結果意外不會，作者好人一生平安…
補充一下，我DFS的方法很笨，就是對字元二維陣列遍歷，搭配布林陣列
每找到一個在布林陣列中是false(代表沒走過)的，我就dfs，再設為true
AC code
#include<bits/stdc++.h>
using namespace std;
int n,m,g,mean;
char c[10005][10005];
bool ta[10005][10005];
map<char,int>mp;
vector<pair<char,int>>vmp;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int nowx,int nowy,char now){
int gx,gy;
for(int x=0;x<4;x++){
gx=nowx+dx[x];
gy=nowy+dy[x];
if(!ta[gx][gy] && (gx>=1 && gx<=n) && (gy>=1 && gy<=m) && c[gx][gy]==now){
ta[gx][gy]=true;
dfs(gx,gy,now);
}
}
}
bool cmp(const pair<char,int>&v1,const pair<char,int>&v2){
if(v1.second==v2.second){
return (v1.first)<(v2.first);
}
return v1.second>v2.second;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> g;
mean=g;
while(g--){
cin >> n >> m;
for(int x=1;x<=n;x++){
for(int y=1;y<=m;y++){
cin >> c[x][y];
ta[x][y]=false;
}
}
for(int x=1;x<=n;x++){
for(int y=1;y<=m;y++){
if(!ta[x][y]){
ta[x][y]=true;
mp[c[x][y]]++;
dfs(x,y,c[x][y]);
}
}
}
cout << "World #"<< mean-g << endl;
for(auto it=mp.begin();it!=mp.end();it++){
vmp.push_back(make_pair(it->first,it->second));
}
sort(vmp.begin(),vmp.end(),cmp);
for(auto it=vmp.begin();it!=vmp.end();it++){
cout << it->first << ": " << it->second << endl;
}
mp.clear();
vmp.clear();
}
return 0;
}