Guarding the Farm S（BFS+map，新奇思路）

题目：

P2919 [USACO08NOV] Guarding the Farm S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路：找到数组中最大的值用map存下来，顺便存一下坐标，然后遍历BFS

#include<bits/stdc++.h>
using namespace std;

#define fir first
#define sec second
#define endl "\n"   

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
const int N = 710, M = N * 2, mod = 1e9 + 7, inf = 0x3f3f3f3f, P = 131;
int g[N][N];
bool st[N][N];
int n,m,ans;
int dx[8]={0,0,1,1,1,-1,-1,-1};
int dy[8]={1,-1,1,0,-1,1,0,-1};
void bfs(int x,int y){
    queue<pii>q;
    q.push({x,y});
    st[x][y]=1;
    while(!q.empty()){
        pii tp=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int x1=tp.fir+dx[i],y1=tp.sec+dy[i];
            if(x1<1||x1>n||y1<1||y1>m) continue;
            if(st[x1][y1]) continue;
            if(g[x1][y1]<=g[tp.fir][tp.sec]){
                st[x1][y1]=1;
                q.push({x1,y1});
            }
        }
    }
}
void solve()
{
    cin >> n >> m;
    map<int,vector<pii>>mp;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> g[i][j];
            mp[-g[i][j]].push_back({i,j});//找最大值存坐标
        }
    }
    for(auto v:mp){
        for(auto t:mp[v.fir]){//取出坐标
            int i=t.fir,j=t.sec;
            if(!st[i][j]){
                    ans++;
                    bfs(i,j);//BFS把山丘标记
            }
        }
    }
    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}