Đỉnh

Thuộc phần Nền tảng cơ bản trong hành trình C của Coddy. Bài học 62 trên 63.

Thử thách

Bạn được cho một lưới 2D gồm các độ cao số nguyên, biểu diễn bản đồ địa hình. Một ô được gọi là đỉnh nếu giá trị của ô đó lớn hơn hẳn giá trị của tất cả các ô lân cận (tối đa 8 ô: phía bắc, phía nam, phía đông, phía tây và bốn đường chéo).

Quy tắc

8 ô lân cận: Bạn phải kiểm tra các ô phía bắc, phía nam, phía đông, phía tây và cả bốn ô trên đường chéo.
Ô ở biên: Ô nằm ở cạnh hoặc góc có ít hơn 8 ô lân cận. Ô đó vẫn là đỉnh nếu giá trị của nó lớn hơn hẳn giá trị của tất cả các ô lân cận đang tồn tại.
Lớn hơn hẳn: Nếu ô lân cận có độ cao bằng ô hiện tại, ô hiện tại không phải là đỉnh.

Đầu vào

Hai số nguyên N và M biểu thị số hàng và số cột.
Một lưới số nguyên có kích thước N*M

Đầu ra

Một số nguyên biểu thị tổng số đỉnh.
Tọa độ (hàng và cột, đánh chỉ số từ 0) của từng đỉnh, được sắp xếp theo hàng trước rồi đến cột.

Ví dụ với đầu vào sau:

Đầu ra là:

Giải thích Các đỉnh nằm ở những vị trí sau:

(0,4) có độ cao 4: Lớn hơn các ô lân cận (3, 1, 1).
(1,0) có độ cao 5: Lớn hơn các ô lân cận (1, 2, 1, 1, 1).
(2,2) có độ cao 9: Lớn hơn cả 8 ô xung quanh có giá trị 1.
(4,1) có độ cao 3: Lớn hơn các ô lân cận (2, 1, 1, 1, 1).
(4,3) có độ cao 4: Lớn hơn các ô lân cận (1, 1, 1, 2, 1).

Tự làm thử

#include <stdio.h>

#define MAXN 100
#define MAXM 100

int N, M;
int grid[MAXN][MAXM];

/**
 * Trả về 1 nếu ô tại (r, c) là đỉnh, ngược lại trả về 0.
 * Ô đỉnh phải có giá trị lớn hơn tất cả ô lân cận hiện có.
 */
int is_peak(int r, int c) {
    // TODO: Xác định vị trí tương đối của 8 ô lân cận
    // (phía bắc, nam, đông, tây và 4 hướng chéo).
    
    // TODO: Duyệt qua từng ô lân cận.
    // GỢI Ý QUAN TRỌNG: Trước khi kiểm tra grid[nr][nc], bạn PHẢI bảo đảm 
    // nr và nc nằm trong giới hạn (từ 0 đến N-1 và từ 0 đến M-1).
    
    return 1; // Phần giữ chỗ
}

int main() {
    // Đọc kích thước
    if (scanf("%d %d", &N, &M) != 2) {
        return 1;
    }

    // TODO: Đọc các giá trị của lưới từ stdin bằng các vòng lặp lồng nhau.
    
    // TODO: Duyệt qua mọi ô (i, j) trong lưới.
    // Nếu is_peak(i, j) trả về true, hãy lưu tọa độ.
    // Bạn có thể dùng hai mảng (array) như peak_r[MAXN*MAXM] và peak_c[MAXN*MAXM] 
    // để lưu kết quả trước khi in ra.

    // TODO: In ra tổng số đỉnh.
    
    // TODO: In ra từng cặp (row, col) đã lưu. 
    // Vì bạn duyệt theo hàng rồi đến cột, các cặp đã được sắp xếp đúng thứ tự!

    return 0;
}

Tất cả bài học trong Nền tảng cơ bản

1Giới thiệu

Ngôn ngữ C Hello World!Chú thích Cấu trúc chương trình cơ bản

4Luồng điều khiển

Câu lệnh if If - else Else-if Switch case Toán tử điều kiện ba ngôi Thử thách ôn tập If - else lồng nhau

7Hàm

Khai báo hàm Kiểu trả về Tham số Thử thách ôn tập #1 Cơ bản về đệ quy Nguyên mẫu hàm Thử thách ôn tập #2

Tự luyện tập: Trình biên dịch C online