Bảo vệ nông trang

Xem dạng PDF
Gửi bài giải
Điểm: 0,14 (OI)
Giới hạn thời gian: 0.38s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
USACO November 2008
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này.

Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt ~1~ người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm ~N~ ~(1 < N \le 700)~ hàng và ~M~ ~(1 < M \le 700)~ cột. Mỗi phần tử của ma trận là độ cao ~H_{ij}~ so với mặt nước biển ~(0 \le~ ~H_{ij}~ ~\le 10~, ~000)~ của ô ~(i~, ~j)~. Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là ~1~ hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ ~X~ không quá ~1~ và chênh lệch tọa độ ~Y~ không quá ~1~.

Input

  • Dòng ~1~: Hai số nguyên cách nhau bởi dấu cách: ~N~ và ~M~
  • Dòng ~2~...~N + 1~: Dòng ~i + 1~ mô tả hàng ~i~ của ma trận với ~M~ số nguyên cách nhau bởi dấu cách: ~H_{ij}~

Output

  • Dòng ~1~: Một số nguyên duy nhất là số lượng đỉnh đồi.

Sample Input

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

Sample Output

3

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    pppssslc  đã bình luận lúc 23, Tháng 5, 2025, 14:04 ← sửa 2
    Spoil!!!

    Tham lam + Loang(DFS):

    • Sort các ô theo thứ tự giảm dần về độ cao.
    • Duyệt các ô theo thứ tự giảm dần:
    • Nếu ô đó đã loang qua thì bỏ qua luôn.
    • Bắt đầu loang tại ô này.
    • Tại mỗi ô X, xét 8 ô Y xung quanh ô X, nếu độ cao ô Y nhỏ hơn hoặc bằng ô X thì ta loang qua ô Y.
    • Đáp án là số ô có thể bắt đầu loang.

    Code:

    #include <bits/stdc++.h> 
#define str string
#define ll long long
#define db double
#define pii pair<int, int>
#define piii pair<int, pii>
#define piiii pair<pii, pii>
#define se second
#define fi first
#define vi vector<int>
#define vii vector<vector<int>>
#define mpii map<int, int>
#define umpii unordered_map<int, int>
#define si set<int>
#define usa unordered_set<int>
#define mulsi multiset<int>
using namespace std;

const int mod=1e9+7;
const int maxn=702;

bool mark[maxn][maxn];
int h[maxn][maxn];
piii nodes[maxn*maxn];
int n, m, cnt, ans;

vi dx={-1, -1, -1, 0, 0, 1, 1, 1};
vi dy={-1, 0, 1, -1, 1, 0, -1, 1};

void dfs(int x, int y){
    if(mark[x][y] || x < 1 || y < 1 || n < x || m < y)return;
    mark[x][y]=true;
    for(int i=0; i < 8; ++i)if(h[x][y] >= h[x+dx[i]][y+dy[i]])dfs(x+dx[i], y+dy[i]);
    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i=1; i <=  n; ++i)for(int j=1; j <= m; ++j){
        cin >> nodes[cnt].fi;
        nodes[cnt].se.fi=i;
        nodes[cnt++].se.se=j;
        h[i][j]=nodes[cnt-1].fi;
    }
    sort(nodes, nodes+cnt);
    for(int i=cnt-1; i >= 0; --i)if(!mark[nodes[i].se.fi][nodes[i].se.se]){
        ++ans;
        dfs(nodes[i].se.fi, nodes[i].se.se);
    }
    cout << ans;
    return 0;
}

  • 1
    manhvuvanyeuha  đã bình luận lúc 20, Tháng 4, 2025, 11:38

    bài tương tựhttps://lqdoj.edu.vn/problem/nkguard


  • 0
    phannam310810  đã bình luận lúc 15, Tháng 4, 2025, 5:45 ← chỉnh sửa

    tai sao output khong phai la 4 vay a


    • -1
      Dangheo  đã bình luận lúc 21, Tháng 5, 2025, 17:21

      2 ô kề nhau khi chênh lệch x và y không quá 1 không phải chung cạnh


    • 1
      manhvuvanyeuha  đã bình luận lúc 20, Tháng 4, 2025, 11:36 ← chỉnh sửa

      đếm đỉnh đồi chứ không phải đếm thành phần liên thông nhé !